51nod1439 互质对 [莫比乌斯函数, 容斥]

$互质对$

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

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

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

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

---

$color{blue}{最初想法}$

考虑每次 $加入/删除$ 一个数字对答案的影响,

将数字 $x$ 分解质因数, 发现可以通过把质因子记录在 桶 内快速得知数 $x$ 与集合中哪些质因子重复, 但是不知道质因子具体属于哪些数 .

---

$color{red}{正解部分}$

分解质因子 $ightarrow$ 分解因子 $=AC$ , 一步之遥= =

现在的目标是: $x$ 与集合内的多少数字互质 .
设 $x = p_1*p_2*...*p_m$, (指数懒得打了…),

分解因子后存到对应的桶 $cnt[]$ 里,

$num_{互质}=tot - cnt[p_1]-cnt[p_2]-...+cnt[p_1*p_2]+...-...+...$ .

容斥系数为 莫比乌斯函数, 没学过的可以看 这里 .

---

$color{red}{实现部分}$

像这种数组下标和值容易混淆的题目, 要注意区分 …

#include<cstdio>
#include<cstring>
typedef long long ll;
#define reg register

//{{{ define
const int maxn = 5e5 + 10;

int N;
int Q;
int p_cnt;
int A[maxn];
int p[maxn];
int mu[maxn];
bool Used[maxn];

ll Ans;
ll cnt[maxn];
//}}}


void sieve(){
        mu[1] = 1;
        for(reg int i = 2; i < maxn; i ++){
                if(!Used[i]) p[++ p_cnt] = i, mu[i] = -1;
                for(reg int j = 1, t; j <= p_cnt && (t = p[j]*i) < maxn; j ++){
                        Used[t] = 1;
                        if(i % p[j] == 0){ mu[t] = 0; break ; };
                        mu[t] = -mu[i];
                }
        }
} //

void Add(int x){
        for(reg int d = 1; d*d <= x; d ++){
                if(x % d) continue ;
                Ans += mu[d] * (cnt[d] ++);
                int d2 = x / d;
                if(d != d2) Ans += mu[d2] * (cnt[d2] ++);
        }
}

void Del(int x){
        for(reg int d = 1; d*d <= x; d ++){
                if(x % d) continue ;
                Ans -= mu[d] * (-- cnt[d]);
                int d2 = x / d;
                if(d != d2) Ans -= mu[d2] * (-- cnt[d2]);
        }
}

void Work(){
        int x;
        scanf("%d", &x);
        !Used[x]?Add(A[x]):Del(A[x]);
        Used[x] ^= 1;
        printf("%lld
", Ans);
}

int main(){
        scanf("%d%d", &N, &Q);
        for(reg int i = 1; i <= N; i ++) scanf("%d", &A[i]);
        sieve(); memset(Used, 0, sizeof Used);
        while(Q --) Work();
        return 0;
}