[题解]洛谷P2257-YY的GCD

Posted on Edited on In

**本文思路部分来自于这篇题解*:凄魉 题解 P2257 【YY的GCD】

题意

多组数据,求 \[ \sum_{i = 1}^n\sum_{j = 1}^m [\gcd(i,j) == k],k \in prime \]

\(T = 10^4,1 \leq n,m \leq 10^7\)

思路

前置

首先我们在求 \[ \sum_{i = 1}^n\sum_{j = 1}^m [\gcd(i,j) == 1] \]

时有这么一种做法,利用了莫比乌斯函数\(\mu\)的性质: \[ \sum_{d|n}\mu(d) = [n = 1] \]

\[ \begin{align} &\sum_{i=1}^{n}\sum_{i=1}^{m}[\gcd(i,j) == 1] \\ &=\sum_{i=1}^{n}\sum_{i=1}^{m}\epsilon(\gcd(i,j))\\ &=\sum_{i=1}^{n}\sum_{i=1}^{m}\sum_{d|gcd(i,j)}\mu(d)\\ &=\sum_{d = 1}^{\min(n,m)}\mu(d)\sum_{i = 1}^n[d|i]\sum_{j = 1}^{m}[d|j]\\ &=\sum_{d=1}^{\min(n,m)}\mu(d)\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d} \rfloor \end{align} \] 那么我们只要构造一个数论函数\(f\),使得 \[ \sum_{d|n}f(d) = [n \in prime] \]

答案就变为了 \[ \sum_{d=1}^{\min(n,m)}f(d)\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d} \rfloor \]

构造方法

形式化地,设数论函数\(g\),构造\(f\)使得\(\sum_{d|n}f(d) = g(n)\)

  1. 对于\(k \in [1,n]\),使\(f(k) = g(k)\)
  2. \(f(n) = f(n) - \sum_{d|n,d \neq n}f(d)\)

如此,我们有: \[ \sum_{d|n}f(d) = \sum_{d|n,d \neq n}f(d) + f(n) = g(n) \] 第二步可以采用类似埃氏筛的方法,复杂度\(O(n\ln n)\)

1
2
3
for(int i = 1;i < maxn;i++)f[i] = g[i];
for(int i = 1;i < maxn;i++)
	for(int j = i+i;j < maxn;j += i)f[j] -= f[i];

对于本题,我们设\(g(n) = [n \in prine]\)即可,可以在\(O(n)\)时间内筛出\(g\).

总复杂度:\(O(n + n\ln n + T \sqrt{\min(n,m)})\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//P2257
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7+10;
int f[maxn];
bool not_p[maxn];
vector<int>prime;
void sieve(){
	not_p[1] = 1;
	for(int i = 2;i < maxn;i++){
		if(!not_p[i]){
			f[i] = 1;
			prime.push_back(i);
		}
		for(int p:prime){
			if(ll(p)*i >= maxn)break;
			not_p[p*i] = 1;
			if(i%p == 0)break; 
		}
	}
	for(int i = 1;i < maxn;i++)
		for(int j = i+i;j < maxn;j += i)f[j] -= f[i];
	for(int i = 1;i < maxn;i++)f[i] += f[i-1];
}
ll cal(int x,int y){
	ll tans = 0;
	for(int l = 1,r = 0;l <= min(x,y);l = r+1){
		r = min(x/(x/l),y/(y/l));
		tans += 1LL*(f[r] - f[l-1])*(x/l)*(y/l);
	}
	return tans;
}
int main(){
	sieve();
	ios::sync_with_stdio(0); 
	int t;
	cin >> t;
	while(t--){
		int n,m;
		cin >> n >> m;
		cout << cal(n,m) << endl;
	}
	return 0;
}

PS.不是我不喜欢用行间公式,是hexo渲染行间LaTex总出奇怪的bug,凑合着看吧=-=

另一种做法

以下均有\(k \in prime\) \[ \begin{align} &\sum_{k = 1}^n\sum_{i = 1}^n\sum_{j = 1}^n[\gcd(i,j) == k]\\ &=\sum_{k = 1}^n\sum_{i = 1}^{\frac{n}{k}}\sum_{j = 1}^{\frac{m}{k}}[\gcd(i,j) == 1]\\ &=\sum_{k = 1}^n\sum_{i = 1}^{\frac{n}{k}}\sum_{j = 1}^{\frac{m}{k}}\sum_{d|\gcd(i,j)}\varphi(d)\\ &=\sum_{k = 1}^n\sum_{d = 1}^{\frac{n}{k}}\varphi(d)\cdot \lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor\\ &设T = kd,枚举T\\ &=\sum_{k = 1}^n\sum_{d=1}^{\frac{n}{k}}\varphi(d)\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\\ &=\sum_{T = 1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{k|T}\mu(\frac{T}{k}) \end{align} \] 可以看出\(f(T) = \sum_{k|T}\mu(\frac{T}{k})\)可以预处理

复杂度:不会

1
2
3
for(int p:prime){
	for(int j = 1;1ll*j*p < maxn;j++)f[j*p] += mu[j];
}

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//P2257_2 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7+10;
bool not_p[maxn];
int mu[maxn];
ll f[maxn];
vector<int>prime;
void sieve_mu(){
	mu[1] = not_p[1] = 1;
	for(int i = 2;i < maxn;i++){
		if(!not_p[i]){
			prime.push_back(i);
			mu[i] = -1;
		}
		for(int p:prime){
			if(1ll*p*i >= maxn)break;
			not_p[i*p] = 1;
			if(i%p)mu[i*p] = -mu[i];
			else{
				mu[i*p] = 0;
				break;
			}
		}
	}
	for(int p:prime){
		for(int j = 1;1ll*j*p < maxn;j++)f[j*p] += mu[j];
	}
	for(int i = 1;i < maxn;i++)f[i] += f[i-1];
}
ll cal(int n,int m){
	ll tans = 0;
	for(int l = 1,r = 0;l <= min(n,m);l = r+1){
		r = min(n/(n/l),m/(m/l));
		tans += (f[r] - f[l-1])*(n/l)*(m/l);
	}
	return tans;
}
signed main(){
	sieve_mu();
	int t;
	cin >> t;
	while(t--){
		int n,m;
		cin >> n >> m;
		cout << cal(n,m) << endl;
	}
	return 0;
}