Note
In first sample test, buying one card is not enough: for example, if you buy a card with length 100, you can’t jump to any cell whose index is not a multiple of 100. The best way is to buy first and second card, that will make you be able to jump to any cell.
In the second sample test, even if you buy all cards, you can’t jump to any cell whose index is not a multiple of 10, so you should output -1.
题意是给出n个数，要求找出其中几个数，可以生成数轴上所有的数，其实，发现只要能生成1,就能生成所有的数，要生成1，，则必然这n个数gcd为1
这样就转化成了gcd的问题！要求某几个数gcd是1，可以用dp思想，从头到尾枚举所有的数，因为数太大，所以生成的数用map set存，这样查询logn复杂度，总的复杂度为n*m*logn
#define INF9000000000000000000#define EPS(double)1e-9#define mod1000000007#define PI3.14159265358979//*******************************************************************************/#endif#define N 100005#define MOD 1000000000000000007int n,l[N],pri[N];map<int,int> mymap;map<int,int>::iterator it;int main(){while(S(n)!=EOF){mymap.clear();FI(n){S(l[i]);}FI(n){S(pri[i]);if(mymap.count(l[i])){mymap[l[i]] = min(mymap[l[i]],pri[i]);}elsemymap[l[i]]=pri[i];}FI(n){for(it=mymap.begin();it != mymap.end();it++){int t = it->first,val = it->second;int temp = gcd(t,l[i]);if(mymap.count(temp)){mymap[temp] = min(mymap[temp],val + pri[i]);}elsemymap[temp] = val + pri[i];}}printf("%d\n",mymap.count(1)?mymap[1]:-1);}return 0;}
只有经历过地狱般的折磨，才有征服天堂的力量。
