codeforces 547c// Mike and Foam// Codeforces Round #305(Div. 1)

题意：给出数组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 ;

}