题意：给出数组arr和一个空数组dst。从arr中取出一个元素到dst为一次操作。问每次操作后dst数组中gcd等于1的组合数。
由于数据都小于10^6，先将10^6以下的数分解质因数。具体来说从2开始，将2的倍数全部加2因子（用的vector），3的倍数加3因子。4不是质数，它的倍数不加因子。
还要一个cnt数组记录dst中有几个数是数组下标的倍数。
在放入元素x到dst数组，对于它的每个质因数及质因数间的乘积，看cnt中的量。组合数的增量为dst的sz(size)-(cnt[x的质因数])（即dst中和x都有x的质因数，因此要减）+（cnt[x的两个质因数的乘积])......然后再对x的素因子及成绩在cnt上加1.
乱码：
//#pragma comment(linker,"/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<vector> #include<cmath> #include<queue> #include<stack> #include<map> #include<set> #include<algorithm> #include <stack> #include <list> using namespace std; const int SZ=1000010,INF=0x7FFFFFFF; typedef long long lon; const double EPS=1e-9; vector<lon> fen[SZ]; bool used[SZ]; lon cnt[SZ];void init(lon n) {for(int i=2;i<n;++i){if(fen[i].empty())for(int j=i;j<n;j+=i){fen[j].push_back(i);}} }void add(vector<lon> &vct,bool type) {lon sz=vct.size();for(lon i=0;i<(1<<sz);++i){lon res=1;for(lon j=0;j<6;++j){if(i&(1<<j)){res*=vct[j];}}if(type)++cnt[res];else --cnt[res];} }lon work(vector<lon> &vct) {lon ans=0;lon sz=vct.size();//cout<<" "<<sz<<endl;for(lon i=1;i<(1<<sz);++i){lon res=1;lon co=1;for(lon j=0;j<6;++j){if(i&(1<<j)){res*=vct[j];co*=-1;}}ans+=co*cnt[res];}return ans; }int main() {std::ios::sync_with_stdio(0);//freopen("d:\\1.txt","r",stdin); lon n,m;cin>>n>>m;vector<lon> vct(n);for(int i=0;i<n;++i){cin>>vct[i];}init(5e5+10);lon num=0;lon last=0;for(int i=0;i<m;++i){lon id;cin>>id;--id;lon res=0;if(!used[id]){res+=work(fen[vct[id]]);//cout<<" "<<res<<endl;add(fen[vct[id]],1);used[id]=1;res=last+res+num;}else{res=last;add(fen[vct[id]],0);lon val=work(fen[vct[id]]);//cout<<" "<<val<<endl;res-=num-1+work(fen[vct[id]]);//cout<<" "<<res<<endl;used[id]=0;}cout<<res<<endl;if(used[id])++num;else --num;last=res;}return 0; }