题意：给出数组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=,INF=0x7FFFFFFF;
typedef long long lon;
const double EPS=1e-;
vector<lon> fen[SZ];
bool used[SZ];
lon cnt[SZ]; void init(lon n)
{
for(int i=;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=;i<(<<sz);++i)
{
lon res=;
for(lon j=;j<;++j)
{
if(i&(<<j))
{
res*=vct[j];
}
}
if(type)++cnt[res];
else --cnt[res];
}
} lon work(vector<lon> &vct)
{
lon ans=;
lon sz=vct.size();
//cout<<" "<<sz<<endl;
for(lon i=;i<(<<sz);++i)
{
lon res=;
lon co=;
for(lon j=;j<;++j)
{
if(i&(<<j))
{
res*=vct[j];
co*=-;
}
}
ans+=co*cnt[res];
}
return ans;
} int main()
{
std::ios::sync_with_stdio();
//freopen("d:\\1.txt","r",stdin);
lon n,m;
cin>>n>>m;
vector<lon> vct(n);
for(int i=;i<n;++i)
{
cin>>vct[i];
} init(5e5+);
lon num=;
lon last=;
for(int i=;i<m;++i)
{
lon id;
cin>>id;
--id;
lon res=;
if(!used[id])
{
res+=work(fen[vct[id]]);
//cout<<" "<<res<<endl;
add(fen[vct[id]],);
used[id]=;
res=last+res+num;
}
else
{
res=last;
add(fen[vct[id]],);
lon val=work(fen[vct[id]]);
//cout<<" "<<val<<endl;
res-=num-+work(fen[vct[id]]);
//cout<<" "<<res<<endl;
used[id]=;
}
cout<<res<<endl;
if(used[id])++num;
else --num;
last=res;
}
return ;
}