这次没有链接== 题目是qz1z买的好像==
听说标解是状压容斥……？
但是我好像直接用莫比乌斯函数乱搞过去了
翻译一下题目
动态求解 $sum_{1<=i<=n}sum_{1<=j<=n}[gcd(a_i,a_j)==1]$
一看就长得一脸莫比乌斯样 这种简单数论题都被做烂了……
根据莫比乌斯函数的性质
变成$sum_{1<=i<=n}sum_{1<=j<=n}sum_{d|gcd(a_i,a_j)}μ(d)$
把枚举因数提前
变成$sum_{d=1}^{n}μ(d)sum_{i=1}^{n}[d|a_i]sum_{j=1}^{n}[d|a_j]$
然后就发现后面两个求和的答案是$d$是多少个数的因数的答案的平方
于是我们就$sqrt{a_i}$地维护这个答案就可以了
Code:
#pragma GCC optimize("Ofast") #pragma GCC optimize("inline", "fast-math", "unroll-loops", "no-stack-protector") #pragma GCC diagnostic error "-fwhole-program" #pragma GCC diagnostic error "-fcse-skip-blocks" #pragma GCC diagnostic error "-funsafe-loop-optimizations" #include <bits/stdc++.h> using namespace std; const int n=500000; int N,Q; bool flag; bool vis[500005]; int mu[500005],cnt[500005],Prime[500005],a[500005],IsPrime[500005],Index; void read(int &t) { char c; while (c=getchar()) if (47<c&&c<58) break; t=c-48; while (c=getchar()) if (47<c&&c<58) t=(t<<3)+(t<<1)+c-48; else break; } void Pre(){ mu[1]=1; for (int i=2;i<=n;i++) { if (!IsPrime[i]){ Index++; Prime[Index]=i; mu[i]=-1; } for (int j=1;j<=Index&&i*Prime[j]<=n;j++) { IsPrime[i*Prime[j]]=true; if (i%Prime[j]==0) break; else mu[i*Prime[j]]=-mu[i]; } } } int main(){ read(N); read(Q); for (int i=1;i<=N;i++) read(a[i]); long long ans=0; Pre(); while (Q--){ int opt; read(opt); int xs; if (!vis[opt]) xs=1; else xs=-1; vis[opt]=1-vis[opt]; int now=a[opt]; if (a[opt]==1) flag=vis[opt]; for (int i=1;i*i<=now;i++){ if (now%i==0){ int R=cnt[i]; ans=ans-(1ll*R*R*mu[i]); cnt[i]+=xs; R=cnt[i]; ans=ans+(1ll*R*R*mu[i]); if((now/i)!=i){ R=cnt[now/i]; ans-=(1ll*R*R*mu[now/i]); cnt[now/i]+=xs; R=cnt[now/i]; ans+=(1ll*R*R*mu[now/i]); } } } printf("%lld ",ans-flag>>1); } return 0; }
--------------------------分割线---------------------------------
2019.10.23 upd
因为一些原因结果还是把状压的做法写了……就顺手写一下题解吧==
考虑一个数字新加进来的时候能产生什么贡献
考虑它的质因数
对于一个有$k$个质因数的$a$
我们去枚举它的子集
根据容斥原理 $ans(S)$=$(-1)^{|T|}*d(T)$ $T⊆S$
因为$2*3*5*7*11*13*17$>$500000$
所以每个数最多$6$个质因子
直接状压完事==
注意枚举的边界==
#include <bits/stdc++.h> using namespace std; int N,Q,anss; int a[100005],cnt[500005],Len; bool used[100005]; int qwq[20]; int Prime[50005]; int Index; int T; bool IsPrime[500005]; inline void Pre(){ for (int i=2;i<=500001;i++){ if (!IsPrime[i]){ Index++; Prime[Index]=i; } for (int j=1;j<=Index&&i*Prime[j]<=500001;j++){ IsPrime[i*Prime[j]]=true; if (i%Prime[j]==0) break; } } } inline int Con(int x){ int ans=0; for (;x;x-=(x&(-x)),ans++); return ans; } inline int Tes(int x){ long long qwqq=1; for (int i=0;i<Len;i++) if (x&(1<<i)) qwqq=1ll*qwqq*qwq[i]; return cnt[qwqq]; } inline int Get_ans(int x){ long long qwqq=1; for (int i=0;i<Len;i++) if (x&(1<<i)) qwqq=1ll*qwqq*qwq[i]; return qwqq; } int main(){ scanf("%d%d",&N,&Q); Pre(); Index=505; for (int i=1;i<=N;i++) scanf("%d",&a[i]); while (Q--){ int opt; scanf("%d",&opt); int now=a[opt]; int noww=now; Len=0; for (int i=1;i<=Index;i++){ if (noww%Prime[i]==0){ qwq[Len++]=Prime[i]; while (noww%Prime[i]==0) noww/=Prime[i]; } if (noww==1) break; } if (noww!=1) qwq[Len++]=noww; int ans=0; int st=(1<<Len)-1; if (used[opt]) for (int i=0;i<=st;i++) cnt[Get_ans(i)]--; for (int i=0;i<=st;i++){ int qwqq=Con(i); int xs=0; if (qwqq%2==0) xs=1; else xs=-1; ans+=xs*Tes(i); } if (used[opt]) anss-=ans; else{ for (int i=0;i<=st;i++) cnt[Get_ans(i)]++; anss+=ans; } used[opt]=(1-used[opt]); printf("%d ",anss); } return 0; }