题解 P2257 【YY的GCD】

题目链接

Solution YY的GCD

题目大意:求(sum_{i=1}^{n}sum_{j=1}^{m}[gcd(i,j) ext{是素数}])

莫比乌斯反演

---

解析：

首先我们定义函数(f(x) = egin{cases}1 & ext{x是素数} \ 0 & ext{其他情况}end{cases})

我们要求的就是：

(sum_{i=1}^{n}sum_{j=1}^{m}f(gcd(i,j)))

然后(d mid gcd(i,j) Longleftrightarrow d | i,d|j)

假设我们找到了一个函数(g)，满足：

[f(x)=sum_{dmid x}g(x) ]

那么

[egin{aligned} ans&=sum_{i=1}^{n}sum_{j=1}^{m}sum_{dmid i,dmid j}g(d) \ &= sum_{d=1}^{min(n,m)}g(d)sum_{i=1}^{n}sum_{j=1}^{m}[d mid i][d mid j] \ &= sum_{d=1}^{min(n,m)}g(d){lfloor frac{n}{d} floor lfloor frac{m}{d} floor}end{aligned} ]

假如我们预处理出(g)的前缀和，利用整除分块我们便可以快速求出整个式子的值

我们尝试着把(g)表示出来

[f = g * 1 Longleftrightarrow g = f * mu ]

[egin{aligned}g(x)&=sum_{d mid x}[x ext{是素数}]mu(frac{x}{d}) \ &= sum_{p mid x}mu(frac{x}{p}) quad ext{p是素数}end{aligned} ]

求(g)我们可以筛出(mu)，然后枚举每一个素数，计算它的贡献

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 100;
int g[maxn],mu[maxn],vis[maxn];
inline int query(int a,int b){return g[b] - g[a - 1];}
vector<int> pri;
inline void init(){
	mu[1] = 1;
	for(int i = 2;i <= maxn;i++){
		if(!vis[i]){
			pri.push_back(i);
			mu[i] = -1;
		}
		for(int x : pri){
			if(i * x >= maxn)break;
			vis[i * x] = 1;
			if(i % x){
				mu[i * x] = mu[i] * mu[x];
			}else{
				mu[i * x] = 0;
				break;
			}
		}
	}
	for(int x : pri)
		for(int i = 1;i * x < maxn;i++)
			g[i * x] += mu[i];
	for(int i = 1;i < maxn;i++)g[i] += g[i - 1];
}
int t,n,m;
inline void solve(){
	cin >> n >> m;
	ll ans = 0;
	for(int l = 1,r;l <= min(n,m);l = r + 1){
		r = min(n / (n / l),m / (m / l));
		ans += (ll)query(l,r) * (n / l) * (m / l);
	}
	cout << ans << '
';
}
int main(){
	init();
	cin >> t;
	while(t--)solve();
	return 0;
}