题目链接
题目分析
由 $gcd(x,y)=p$ 可以推出 $p|x,p|y$,即
则原式变为
即求解
则问题便可以用欧拉函数求解
代码实现
cpp
#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;
}