题意：给出1000个数，和一个整数10^12。求个数最少，和最小的子集，使得他们的乘积是时k的倍数。
题解：注意到k的约束的个数不是很大，然后dp[i][d]=dp[i][d/gcd(a[i],d])]+1;注意到只有k的约束的才有意义，然后就是离散化，然后dp，细节比较多，请查看代码。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL,LL> pLL; /* 1.离散化 2.dp */ #define N 1001000 vector<pLL> primeDiviser; vector<vector<int> > aiConPi; vector<int> mul; int init(vector<LL> a,int n,LL k){ //vector<bool> isPrim(N,true); for(LL i=2;i*i<=k;i++){ //if(!isPrim[i]) continue; // for(LL j=i*i;j<N;j++){ // isPrim[j] = false; // } if(k%i==0){ pLL tmpPrimeDiviser = make_pair(i,0); while(k%i==0){ tmpPrimeDiviser.second++; k/=i; } primeDiviser.push_back(tmpPrimeDiviser); } } if(k!=1){ primeDiviser.push_back(make_pair(k,1)); } //每个数包含的k的约数的个数 aiConPi = vector<vector<int> > (n,vector<int>(primeDiviser.size(),0)); for(int i=0;i<n;i++){ for(int j=0;j<(int)primeDiviser.size();j++){ while(a[i]%primeDiviser[j].first==0){ aiConPi[i][j]++; a[i]/=primeDiviser[j].first; } } } //离散化用的 mul = vector<int>(primeDiviser.size(),0); mul[primeDiviser.size()-1] = 1; for(int i=primeDiviser.size()-2;i>=0;i--){ mul[i] = mul[i+1]*(primeDiviser[i+1].second+1); } int ret = 0; for(int i=primeDiviser.size()-1;i>=0;i--){ ret += primeDiviser[i].second*mul[i]; } return ret; //最终的状态 目标状态 //target status的状态是 } const LL INF = (LL)1e18; int main(){ int n; LL k; while(cin>>n>>k){ vector<LL> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } if(k==1){//没有素因子 LL ret = 0; for(int i=1;i<n;i++){ if(a[ret]>a[i]){ ret = i; } } cout<<1<<endl<<ret+1<<endl; continue; } int target = init(a,n,k);//找出全部素因子 //cout<<"target:"<<target<<endl; vector<vector<pLL> > dp(n+1,vector<pLL>(target+1,make_pair(INF,0))); vector<vector<int> > prev(n+1,vector<int>(target+1,-1)); dp[0][0]=make_pair(0,0);// // for(int i=0;i<n;i++){ // for(int j=0;j<(int)primeDiviser.size();j++){ // cout<<aiConPi[i][j]<<" "; // } // cout<<endl; // } // for(int i=0;i<(int)primeDiviser.size();i++){ // cout<<mul[i]<<" "; // } // cout<<endl; for(int i=1;i<=n;i++){ for(int j=0;j<=target;j++){ dp[i][j] = dp[i-1][j]; prev[i][j] = j; int last=0,cur=j; for(int e=0;e<(int)primeDiviser.size();e++){ last += mul[e] * max(0,cur/mul[e]-aiConPi[i-1][e]); cur%=mul[e]; } // cout<<"dp["<<i-1<<"]["<<last<<"]->"<<"dp["<<i<<"]["<<j<<"]"<<endl; if(dp[i][j] > make_pair(dp[i-1][last].first+1,dp[i-1][last].second+a[i-1])){ dp[i][j] = make_pair(dp[i-1][last].first+1,dp[i-1][last].second+a[i-1]); prev[i][j] = last; //cout<<j<<","<<last<<endl; } // cout<<"dp["<<i<<"]["<<j<<"]:"<<dp[i][j].first<<","<<dp[i][j].second<<endl; } } //cout<<"get here"<<endl; if(dp[n][target] == (pLL) make_pair(INF,0)){ cout<<"-1"<<endl; }else{ cout<<dp[n][target].first<<endl; for(int i=n,j=target;i>=1&&j!=0;j = prev[i][j],i--){ if(prev[i][j]==j){ continue; }else{ cout<<i<<" "; } // cout<<j<<endl; } cout<<endl; } } } /* 2 1 1000000000000 999999999999 */
