自动搬运

查看原文

来自洛谷，原作者为

	Siyuan Dream OIer.

搬运于2025-08-24 21:39:10，当前版本为作者最后更新于2019-02-08 10:56:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$$\Large\texttt{My Blog}$$

---

Description

题目链接：Luogu 2568

给定整数 $n$，求 $1\le x,y\le n$ 且 $\gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对。

数据范围：$1\le n\le 10^7$

---

Solution

本题和「Luogu 2257」YY 的 GCD（题解） 几乎完全一样，但是本题由于是单组询问，所以不需要 $O(n)$ 的预处理和 $O(\sqrt n)$ 的单次询问复杂度。

首先我们枚举质数：

$$\sum_{p\in\text{prime}}\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=p] $$

对 $\gcd$ 进行套路式的变形：

$$\sum_{p\in\text{prime}}\sum_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{p}\right\rfloor} [\gcd(i,j)=1] $$

接下来改变 $j$ 的枚举上界（其中 $-1$ 的原因是 $i=j=1$ 时的答案会被重复统计，因此注意这里的 $-1$ 是在 $\sum_{p\in\text{prime}}$ 中的，而不是在 $\sum_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}$ 中的）：

$$\sum_{p\in\text{prime}}\left(\sum_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\left(2\sum_{j=1}^i [\gcd(i,j)=1]\right)-1\right) $$

此已经可以发现最后一个 $\sum$ 是的值就是 $\varphi(i)$，故原式化为：

$$\sum_{p\in\text{prime}}\left(2\sum_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\varphi(i)-1\right) $$

所以我们可以线性筛求出 $\varphi(i)$ 的值并做前缀和，枚举 $p\in\text{prime}\ \text{and}\ p\le n$ 并统计答案即可。

时间复杂度：$O(n)$

---

Code

#include <cstdio>

const int N=1e7+5,M=1e6+5;
int n,tot,p[M],phi[N];
long long sum[N];
bool flg[N];

void sieve(int n) {
	phi[1]=1;
	for(int i=2;i<=n;++i) {
		if(!flg[i]) p[++tot]=i,phi[i]=i-1;
		for(int j=1;j<=tot&&i*p[j]<=n;++j) {
			flg[i*p[j]]=1;
			if(i%p[j]==0) {
				phi[i*p[j]]=phi[i]*p[j];
				break;
			} else {
				phi[i*p[j]]=phi[i]*phi[p[j]];
			}
		}
	}
	for(int i=1;i<=n;++i) sum[i]=sum[i-1]+phi[i];
}
int main() {
	scanf("%d",&n);
	sieve(n);
	long long ans=0;
	for(int i=1;i<=tot;++i) ans+=2*sum[n/p[i]]-1;
	printf("%lld\n",ans);
	return 0;
}