P2568 GCD

题目链接

题目分析

由 $gcd(x,y)=p$ 可以推出 $p|x,p|y$，即

$$\begin{matrix} &x=ap，y=bp \\&a,b\in \left[ 1,\lfloor\frac{n}{p}\rfloor \right] \end{matrix}$$

则原式变为

$$gcd(ap,bp)=gcd(a,b)*p=p$$

即求解

$$\sum\sum_{a=1}^{\lfloor\frac{n}{p_i}\rfloor}\sum_{b=1}^{\lfloor\frac{n}{p_i}\rfloor}(gcd(a,b)=1) = \sum(2*\sum_{a=1}^{\lfloor\frac{n}{p_i}\rfloor}\sum_{b=1}^{a}(gcd(a,b)=1)-1) \\=\sum(2*\sum_{a=1}^{\lfloor\frac{n}{p_i}\rfloor}ψ(a)-1)$$

则问题便可以用欧拉函数求解

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long maxn=1e7+7;
long long f[maxn];//f[i]指 ψ(i)
long long p[maxn],cnt;//p[i]用于存储第i格质数,cnt用于统计素数个数
long long tag[maxn];//tag[i] 用于记录i是否是素数
void euler(long long n)//线性筛选素数,求出 2-n 的所有欧拉函数值
{
	f[1]=1;
	for(long long i=2; i<=n; ++i)
	{
		if(!tag[i])
		{
			p[++cnt]=i;
			f[i]=i-1;//若 a 为质数，则ψ(a)=a-1
		}
		for(long long j=1; j<=cnt&&i*p[j]<=n; j++)
		{
			long long v=i*p[j];
			tag[v]=1;
			if(i%p[j]==0)
			{
				f[v]=f[i]*p[j];//性质3 若 b 为 a 的倍数，则  ψ(a*b)=a*ψ(b)
				break;
			}
			//p[j]的因数只有1和它本身，所以p[j]与i互质，符合性质2
			f[v]=f[i]*f[p[j]];//性质2
		}
	}
}
long long Ans[maxn];//Ans[i] 用于记录f[i]的前缀和
void Slove(ll n)
{
	for(int i=1; i<=n; ++i)
		Ans[i]=Ans[i-1]+f[i];
}
int main()
{
	int n,i;
	ll ans=0;
	cin>>n;
	euler(n);
	Slove(n);
	for(i=1; i<=cnt&&p[i]<=n; ++i)
	{
		ans+=2*Ans[n/p[i]]-1;
	}
	cout<<ans;
	return 0;
}