51Nod 1439：互质对（用莫比乌斯来容斥）

有n个数字，a11,a22,…,ann。有一个集合，刚开始集合为空。然后有一种操作每次向集合中加入一个数字或者删除一个数字。每次操作给出一个下标x(1 ≤ x ≤ n)，如果axx已经在集合中，那么就删除axx,否则就加入axx。

问每次操作之后集合中互质的数字有多少对。

注意，集合中可以有重复的数字，两个数字不同当且仅当他们的下标不同。

比如a11=a22=1。那么经过两次操作1，2之后，集合之后存在两个1，里面有一对互质。

Input单组测试数据。 
第一行包含两个整数n 和 q (1 ≤ n, q ≤ 2 × 10^5)。表示数字的种类和查询数目。 
第二行有n个以空格分开的整数a11,a22,…,ann (1 ≤ aii ≤ 5 × 10^5),分别表示n个数字。 
接下来q行，每行一个整数x(1 ≤ x ≤ n)，表示每次操作的下标。Output对于每一个查询，输出当前集合中互质的数字有多少对。Sample Input

样例输入1

5 6

1 2 3 4 6

1

2

3

4

5

1

样例输入2

2 3

1 1

1

2

1

Sample Output

样例输出1

0

1

3

5

6

2

样例输出2

0

1

0

题意：给定一个数组，现在全部数都没有填进对于的位置上去。现在，有一些操作，或是把a[i]填到i位置，或是把a[i]从i位置取出来。问当前填进去的数列有多少个互质对。

思路：显然可以用容斥定理来做。怎么破？ 对于当前的集合（大小为N），我加一个x进去，会增加多少互质对呢？答案是N-与x不互质的个数。

对于x的所有约数去重，比如N=5；x=24。add=N-有约数2的个数-有约数3个个数+有约数4的个数+有约数6的个数+0*有约数12的个数+0*有约数24的个数。

对于它前面的符号，取决于约数的素因子factor：

如果factor为1，它就是1；

如果factor有平方因子，符号为0；  如12=2*2*3

如果factor有奇数个素数，符号为-1； 如2

如果factor有偶数个素数，符号为1；如6

所以，我们先用筛法得到每个数的约数（O(NlgN)）;

然后加一个数x，用上面的方法，求出多了多少个素数对。我们就对x的所有约数++；

反之亦然；

（不加输出优化会TLE

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=;

int p[maxn+],cnt;

short int vis[maxn+],mu[maxn+];

void read(int &x){  //输入

    x=; char c=getchar();

    while(c>''||c<'') c=getchar();

    while(c>=''&&c<='') x=(x<<)+(x<<)+c-'',c=getchar();

}

void Put(ll x)   //输出

{

    if(x>) Put(x/);

    putchar(x%+'');

}

void prime() //筛莫比乌斯数

{

    mu[]=; for(int i=;i<=maxn;i++){

        if(!vis[i]) p[++cnt]=i,mu[i]=-;

        for(int j=;j<=maxn&&i*p[j]<=maxn;j++){

            vis[i*p[j]]=; mu[i*p[j]]=-mu[i];

            if(i%p[j]==) { mu[i*p[j]]=; break; }

        }

    }

}

int a[],num[maxn+];ll ans;

vector<int>G[maxn+];

int main()

{

    prime();

    int N,Q,x,i,j,Max=;

    scanf("%d%d",&N,&Q);

    for(i=;i<=N;i++) read(a[i]),Max=max(Max,a[i]),vis[i]=;

    for(i=;i<=Max;i++){ //筛约数

      for(j=i;j<=Max;j+=i)

         G[j].push_back(i);

    }

    while(Q--){

        read(x);

        int L=G[a[x]].size();

        if(vis[x]==){

            for(i=;i<L;i++) num[G[a[x]][i]]--;

            for(i=;i<L;i++) ans-=mu[G[a[x]][i]]*num[G[a[x]][i]];

        }

        else {

            for(i=;i<L;i++) ans+=mu[G[a[x]][i]]*num[G[a[x]][i]];

            for(i=;i<L;i++) num[G[a[x]][i]]++;

        }

        vis[x]=vis[x]^;

        Put(ans); puts("");

    }

    return ;

}

51Nod 1439：互质对（用莫比乌斯来容斥）的相关教程结束。