容斥定理所以可以用莫比乌斯函数来搞。逆向思维答案等于总和减去和他互质的。
那么设f[i]=∑a[j] i|j。ans[i]=sum- ∑mo[j]*f[j] 跟bzoj2440那道题挺像的都是利用莫比乌斯函数来做容斥定理。
结果因为修改的时候只修改<sqrt（n）的一直WA。。。吃枣药丸。。。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
int read(){
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}
const int nmax=1e5+5;
const int inf=0x7f7f7f7f;
int a[nmax],f[nmax],mo[nmax],pe[nmax>>3];bool vis[nmax];
int main(){
int n=read(),m=read();rep(i,1,n) a[i]=read();
rep(i,1,n) rep(j,1,n/i) f[i]+=a[i*j];
mo[1]=1;int cnt=0,tp;
rep(i,2,n) {
if(!vis[i]) pe[++cnt]=i,mo[i]=-1;
rep(j,1,cnt){
tp=pe[j];if((ll)i*tp>n) break;vis[i*tp]=1;
if(i%tp==0) {
mo[i*tp]=0;break;
}mo[i*tp]=-mo[i];
}
}
int u,v,d,t,tmp;ll ans=0;
rep(i,1,m){
u=read();
if(u==1) {
v=read(),d=read();t=(int)sqrt(v);tmp=d-a[v];a[v]=d;
rep(j,1,t) if(v%j==0) f[j]+=tmp,f[v/j]+=tmp;
if(t*t==v) f[t]-=tmp;
}else{
v=read();d=(int)sqrt(v);ans=0;
rep(j,1,d) if(v%j==0) ans+=mo[j]*f[j]+mo[v/j]*f[v/j];
if(d*d==v) ans-=mo[d]*f[d];
printf("%lld
",ans);
}
}
return 0;
}
基准时间限制：2 秒 空间限制：131072 KB 分值: 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示例
5 3 1 2 3 4 5 2 4 1 3 1 2 4
Output示例
9 7