1678lyk与gcd基准时间限制：2秒 空间限制：131072KB 分值:80难度：5级算法题
这天，lyk又和gcd杠上了。
它拥有一个n个数的数列，它想实现两种操作。
1：将 ai改为b。
2：给定一个数i，求所有gcd(i,j)=1时的 aj的总和。
Input
第一行两个数n，Q(1<=n,Q<=100000)。接下来一行n个数表示ai(1<=ai<=10^4)。接下来Q行，每行先读入一个数A(1<=A<=2)。若A=1，表示第一种操作，紧接着两个数i和b。(1<=i<=n,1<=b<=10^4)。若B=2，表示第二种操作，紧接着一个数i。(1<=i<=n)。
Output
对于每个询问输出一行表示答案。
Input示例
53123452413124
Output示例
97
思路
考虑辅助数组f[i]表示所有下标为i的倍数的a数组的总和。
例如有5个数，那么f[1]=a[1]+a[2]+a[3]+a[4]+a[5]，f[2]=a[2]+a[4]，f[3]=a[3]，f[4]=a[4]，f[5]=a[5]。
对于每一个修改操作，我们只需要求出i的所有因数，然后将下标为它的因数的f数组中修改值即可。 对于所有询问操作，求出i的所有因数p1,p2,p3...之后答案即为Σu[pi]*f[pi]。 其中u为mobius函数。 总复杂度为所有操作中i的因数个数总和。
利用容斥定理----
先将每个数加到它的约数里---
然后每次利用容斥定理求出和 i 不互素的数的和---
总和-求的和就为所要的解
#include<cstdio> #include<cmath> #include<vector> #include<cstring> #include<algorithm> using namespace std; #define LL long long vector <int > sta[200100]; int shu[220000]; int ou[100],ll; int qu[200100],kkp; LL pp[200100]; void init(int n) { int su[200100],kp=0; bool fa[200100]; memset(fa,true,sizeof(fa)); for (int i=2;i<=n;i++) { if (fa[i]) { su[kp++]=i; if (i<=sqrt(n)) for (int j=i*i;j<=n;j+=i) fa[j]=false; } } for (int i=2;i<=n;i++) { int ll=0; int kk=i; for (int j=0;su[j]*su[j]<=kk;j++) { if (kk%su[j]==0) ou[ll++]=su[j]; while (kk%su[j]==0) kk/=su[j]; } if (kk>1) ou[ll++]=kk; kkp=0; qu[kkp++]=-1; for (int j=0;j<ll;j++) { kk=kkp; for (int k=0;k<kk;k++) qu[kkp++]=qu[k]*ou[j]*-1; } for (int j=1;j<kkp;j++) sta[i].push_back(qu[j]); } } int main() { int n,k; /*freopen("In.txt","r",stdin); freopen("wo.txt","w",stdout);*/ scanf("%d%d",&n,&k); init(n); LL s=0,ans; memset(pp,0,sizeof(pp)); for (int i=1;i<=n;i++) { scanf("%d",&shu[i]); for (int j=0;j<sta[i].size();j++) { if (sta[i][j]>0) pp[sta[i][j]]+=shu[i]; else pp[-sta[i][j]]+=shu[i]; } s+=shu[i]; } int a,b,c; while (k--) { scanf("%d",&c); if (c==1) { scanf("%d%d",&a,&b); for (int j=0;j<sta[a].size();j++) { if (sta[a][j]>0) pp[sta[a][j]]-=shu[a]; else pp[-sta[a][j]]-=shu[a]; } s-=shu[a]; shu[a]=b; for (int j=0;j<sta[a].size();j++) { if (sta[a][j]>0) pp[sta[a][j]]+=shu[a]; else pp[-sta[a][j]]+=shu[a]; } s+=shu[a]; } else { scanf("%d",&a); if (a==1) { printf("%lld\n",s); continue; } ans=0; for (int i=0;i<sta[a].size();i++) { if (sta[a][i]<0) ans-=pp[-sta[a][i]]; else ans+=pp[sta[a][i]]; }ans=s-ans; printf("%lld\n",ans); } } return 0; }
View Code
这道题是我复制借鉴的/leibniz_zhang/article/details/52318715这位大佬的 = =
