给定正整数 \(n\)，求 \(1\le x,y\le n\) 且 \(\gcd(x,y)\) 为素数的数对 \((x,y)\) 有多少对。
\(n\le 10^7\)
题解
做法1
题意即为求\(S=\sum_{质数p|n}\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=p]\)
常规操作化简\(S=\sum_{质数p|n}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}[\gcd(i,j)=1]\)
如果我们记\(n'={\lfloor\frac{n}{p}\rfloor},f(i)=\sum_{a=1}^{n'}\sum_{b=1}^{n'}[\gcd(a,b)=i],g(i)=\sum_{i|d}f(d)\)
则展开\(g(i)\)有
\[g(i)=\sum_{i|d}\sum_{a=1}^{n'}\sum_{b=1}^{n'}[\gcd(a,b)=d] \]常规操作\(g(i)=\sum_{a=1}^{n'}\sum_{b=1}^{n'}\left[i|\gcd(a,b)\right]=\sum_{a=1}^{\lfloor\frac{n'}{i}\rfloor}\sum_{b=1}^{\lfloor\frac{n'}{i}\rfloor}[1|gcd(a,b)]=\left\lfloor\frac{n'}{i}\right\rfloor^2\)
所以\(S=\sum_{质数p|n}f(p)=\sum_{质数p|n}\sum_{d=1}^{dp\le n}\mu\left(d\right)g(p)=\sum_{质数p|n}\sum_{d=1}^{pd\le n}\mu(d)\left\lfloor\frac{n}{dp}\right\rfloor^2\)
接着有设\(T=dp\),这里由于\(p,d\)具有对称性,交换求和次序有\(S=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor^2\sum_{质数p|T}\mu\left({\frac{T}{p}}\right)\)
然后\(\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor^2\)可以整除分块,而后面的可以在筛一遍质数之后\(O(\sqrt{n})\)求出,于是复杂度就是\(O(n)\),实际上远远跑不满
做法2
事实上,因为数对具有对称性,我们可以将\(S\)稍稍变形得到
\(S=\sum_{质数p|n}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}[\gcd(i,j)=1]=\sum_{质数p|n}\left(2\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^i[\gcd(i,j)=1]-1\right)\)
这个\(-1\)是因为不能让\((p,p)\)统计两次,根据\(\varphi\)的定义,会发现原式等价于\(\sum_{质数p|n}\left(2\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i)-1\right)\)
预处理欧拉函数前缀和即可线性求解
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 10000005
#define int long long
int n, phi[N], prime[N], v[N], cnt, s[N];
int init() {
phi[1] = 1;
scanf("%lld", &n);
for (int i = 2; i <= n; i++) {
if (!v[i]) {
v[i] = i;
prime[++cnt] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= cnt; j++) {
if (prime[j] > v[i] || prime[j] * i > n)break;
v[prime[j] * i] = prime[j];
phi[prime[j] * i] = i % prime[j] ? phi[i] * (prime[j] - 1) : phi[i] * prime[j];
}
}
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + phi[i];
}
return 0;
}
void solve() {
int m = n, ans = 0;
for (int i = 1; i <= cnt; i++) {
ans += s[m / prime[i]] << 1;
ans--;
}
printf("%lld", ans);
return;
}
signed main() {
init();
solve();
return 0;
}