http://codeforces.com/contest/703/problem/E
题意：
给出n个数和一个k，计算出至少要多少个数相乘才是k的倍数。
思路：
这道题目参考了杭电大神的代码http://blog.csdn.net/snowy_smile/article/details/52134304。
对于每个数字，我们要么选，要么不选，这就很像01背包。但是肯定是需要预处理的。
对于每个数字，它所贡献的数就是它和k的最大公因数，这个不难理解吧。
所以我们可以把k的所有因子计算出来，因为有些因子很大，所以这里离散化一下，用map映射，这样后面才开得了数组。
我们用f[i][j]表示前i个数字，它们的gcd乘=映射j状态时的最佳方案。
当我们分析到第i个数字时，它所能贡献的数就是gcd（a[i]，v[j]），那么它的前缀就是v[j]/gcd（a[i]，v[j]）,具体参见代码。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
const int maxn=+; int n;
LL k;
LL s;
LL a[maxn];
LL b[maxn];
pair<int,LL> f[maxn][maxn*];
vector<LL> v;
map<LL,LL> key; LL gcd(LL a,LL b)
{
if(a<b) swap(a,b);
while(b!=)
{
LL t=a;
a=b;
b=t%b;
}
return a;
} void dp()
{
if(k==)
{
puts("");
LL tmp =0x3f3f3f3f3f3f3f3f, ans=-;
for (int i = ; i<=n;++i)
if (a[i]<=tmp)
{
ans=i;
tmp=a[i];
}
printf("%lld\n", ans);
return;
}
for(int j=;j<s;j++) f[][j]=make_pair(n+,);
for(int i=;i<=n;i++)
{
for (int j = ; j < s; ++j)
{
f[i][j] = f[i - ][j];
int pre = key[v[j] / gcd(v[j], b[i])];
f[i][j]=min(f[i][j], make_pair(f[i - ][pre].first + , f[i - ][pre].second + a[i]));
}
}
if (f[n][s-].first > n) puts("-1");
else
{
printf("%d\n", f[n][s-].first);
for (int i = n; i; --i)
{
if (f[i][key[k]] != f[i - ][key[k]])
{
printf("%d ", i);
k /= gcd(k, b[i]);
}
}
puts("");
}
} int main()
{
//freopen("D:\\input.txt","r",stdin);
while(~scanf("%d%lld",&n,&k))
{
LL m=sqrt(k+0.5);
v.clear();
for(int i=;i<=m;i++)
{
if(k%i==)
{
v.push_back(i);
if(k/i!=i) v.push_back(k/i);
}
}
sort(v.begin(),v.end());
s=v.size();
key.clear();
for(int i=;i<s;i++) key[v[i]]=i;
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
b[i]=gcd(k,a[i]);
}
dp();
}
return ;
}