51Nod---1678 lyk与gcd （莫比乌斯反演）

题目链接

这天，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

开始做这道题的时候，标签全是容斥原理，但是我把题目公式写出来：，心想明显是一道莫比乌斯反演啊，所以搞得一脸懵逼QAQ。莫比乌斯就莫比乌斯吧，那就管他容斥还是啥，硬着头皮推公式

到这里就推到完成，接下来就可以直接上代码了

#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long int
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 1e5 + 5;
int phi[maxn], miu[maxn], fac[maxn];//phi--欧拉函数表  miu--莫比乌斯函数表  fac--i最大的素因子辅助打phi表
void init()
{
	for (int i = 1; i < maxn; ++i) fac[i] = i;
	phi[1] = miu[1] = 1;
	for (int i = 2; i < maxn; ++i)
	{
		if (fac[i] == i)
			for (int j = i << 1; j < maxn; j += i)
				fac[j] = i;
		if (i / fac[i] % fac[i]) phi[i] = (fac[i] - 1)*phi[i / fac[i]], miu[i] = -miu[i / fac[i]]; //如果b质数  a%b！=0  phi(a*b) = phi(a)*b - phi(a)
		else phi[i] = fac[i] * phi[i / fac[i]], miu[i] = 0;										//当b是质数，a%b==0，phi(a*b)=phi(a)*b 
	}
}
int a[maxn];
int sum[maxn];
void update(int id, int b) {
	for (int i = 1; i*i <= id; i++) {
		if (id%i == 0) {
			sum[i] = sum[i] - a[id] + b;
			if (i*i != id)sum[id/i] = sum[id/i] - a[id] + b;
		}
	}
	a[id] = b;
}
ll query(int x) {
	ll ans = 0;
	for (int i = 1; i*i <= x; i++) {
		if (x%i == 0) { 
			ans += miu[i] * sum[i];
			if (i*i != x)ans += miu[x / i] * sum[x / i];
		}
	}
	return ans;
}
int main() {
	int n, Q,Chose;
	init();
	scanf("%d%d", &n, &Q);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j += i) {
			sum[i] += a[j];
		}
	}
	while (Q--) {
		scanf("%d", &Chose);
		if (Chose == 1) {
			int id, b;
			scanf("%d%d", &id, &b);
			update(id,b);
		}
		else {
			int x;
			scanf("%d", &x);
			printf("%lld\n", query(x));
		}
	}
	return 0;
}