P2568 GCD


题目链接

题目分析

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

则原式变为

即求解

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

代码实现

#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;
}

如果本文帮助到了你,帮我点个广告可以咩(o′┏▽┓`o)


评论
  目录