codeforces 547C 容斥原理

#include<bits/stdc++.h>
using namespace std;
const int maxn = 500005;
int a[200005],mul[80],cnt[maxn],has[200005];
vector<int> p[maxn];
long long ans;
void add(int val,int sign)
{
    for(int mask=0;mask<(1<<p[val].size());mask++)
    {
        if(!mask)
            mul[mask]=1;
        else
            mul[mask]=mul[mask&(mask-1)]*p[val][__builtin_ctz(mask)];
        if(sign<0)
            cnt[mul[mask]]--;
        if(__builtin_popcount(mask)&1)
            ans-=cnt[mul[mask]]*sign;
        else
            ans+=cnt[mul[mask]]*sign;
        if(sign>0)
            cnt[mul[mask]]++;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    for(int i=2;i<maxn;i++)
        if(p[i].empty())
            for(int j=i;j<maxn;j+=i)
                p[j].push_back(i);
    int n,q;
    cin >> n >> q;
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
        has[i]=1;
    }
    while(q--)
    {
        int x;
        cin >> x;
        x--;
        add(a[x],has[x]);
        has[x]*=-1;
        cout << ans << "\n";
    }
    return 0;
}

codeforces 547C 容斥原理

原文：http://blog.csdn.net/u013491149/article/details/46806511