Codeforces547C:Mike and Foam

总是有那么一些人,能把数论题出成数据结构题,那么现在我们来聊一聊动态莫比乌斯反演。
题目大意:

给定两个集合,每次从一个集合里添加或删除另一个集合的数,询问每次操作后互质的数有多少个。

互质当然大力欧拉或者反演啦(虽然这道题正解是容斥)。我们设$f(d)$表示集合里$gcd(i,j)=d$的数对的数目,$g(d)$表示$d|gcd(i,j)$的数对的数目。
老司机们迅速的繁衍反演了一下:
$f(i)= \sum\limits_{i|d} g(d) \mu(\frac{d}{i})$
然后我们考虑如何处理每次询问,我们能不能暴力的记录$g(d)$呢?暴力记录肯定要爆炸蛙,我们考虑一下$\mu(d)$对答案的影响,可以发现我们只需要考虑每个数的无平方因子的因数即可,而每个数的质因数个数不超过$log(N)$个,所以我们暴力枚举因数即可加个$2^6$的常数肯定不会爆炸。
所以每次插入/删除一个数时,维护所以无平方因子的因数$g$,根据这些东西更新答案即可。

//CF 547C
//by Cydiater
//2017.2.23
#include <iostream>
#include <queue>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <bitset>
#include <set>
#include <vector>
#include <complex>
using namespace std;
#define ll long long
#define up(i,j,n)    for(ll i=j;i<=n;i++)
#define down(i,j,n)    for(ll i=j;i>=n;i--)
#define cmax(a,b)    a=max(a,b)
#define cmin(a,b)    a=min(a,b)
const ll MAXN=5e5+5;
const ll LIM=5e5;
inline ll read(){
    char ch=getchar();ll x=0,f=1;
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll prime[MAXN],cnt=0,miu[MAXN],arr[MAXN],label[MAXN],N,Q,wai[MAXN][10],ans=0;
bool vis[MAXN],exi[MAXN];
namespace solution{
    ll Col(ll num){return num*(num-1)>>1;}
    void Prepare(){
        miu[1]=1;
        up(i,2,LIM){
            if(!vis[i]){prime[++cnt]=i;miu[i]=-1;}
            up(j,1,cnt){
                if(i*prime[j]>LIM)break;
                vis[i*prime[j]]=1;
                if(i%prime[j])miu[i*prime[j]]=-miu[i];
                else break;
            }
        }
        N=read();Q=read();
        up(i,1,N){
            arr[i]=read();ll tmp=arr[i];
            wai[i][0]=0;
            up(j,1,cnt){
                if(prime[j]*prime[j]>tmp)break;
                if(tmp%prime[j]==0){
                    wai[i][++wai[i][0]]=prime[j];
                    while(tmp%prime[j]==0&&tmp)tmp/=prime[j];
                }
            }
            if(tmp!=1)wai[i][++wai[i][0]]=tmp;
            sort(wai[i]+1,wai[i]+wai[i][0]+1);
        }
    }
    void Solve(){
        /*up(i,1,N){
            up(j,1,wai[i][0])printf("%d ",wai[i][j]);
            puts("");
        }*/
        while(Q--){
            ll pos=read();exi[pos]^=1;
            //puts("----------------------------");
            for(ll S=1;S<(1<<wai[pos][0]);S++){
                ll num=1;
                up(j,0,wai[pos][0]-1)if((S&(1<<j))==(1<<j))
                    num*=wai[pos][j+1];
                //cout<<num<<endl;
                ans-=Col(label[num])*miu[num];
                label[num]+=exi[pos]?1:-1;
                ans+=Col(label[num])*miu[num];
            }
            ans-=Col(label[1])*miu[1];
            label[1]+=exi[pos]?1:-1;
            ans+=Col(label[1])*miu[1];
            printf("%I64d\n",ans);
        }
    }
}
int main(){
    freopen("input.in","r",stdin);
    using namespace solution;
    Prepare();
    Solve();
    return 0;
}