Description
给定整数\(n\),\(1 \leq x,y \leq n\)且\(gcd(x,y)\)为质数的\((x,y)\)的对数
\[1\leq n\leq 10^7
\]
Solution
\(O(n^2\space log \space n)\)的枚举肯定会爆,所以我们换一个统计方法
从质数入手,所以题意转化为求
\[\sum _ {p \in prime} \sum _ {i=1} ^{n} \sum_{j=1}^n [gcd(i,j)==p]
\]
处理\(gcd\) ,进行套路性变形
\[\sum _ {p \in prime} \sum _ {i=1} ^{\lfloor \frac{n}{p}\rfloor} \sum _ {j=1} ^{\lfloor \frac{n}{p}\rfloor} [gcd(i,j)==1]
\]
下面我们改变\(j\)的枚举上界(就是因为有对称性嘛)
\[\sum _ {p \in prime} \sum _ {i=1} ^{\lfloor \frac{n}{p}\rfloor}(2\times \sum _ {j=1} ^{i} [gcd(i,j)==1]-1)
\]
这里的减\(1\)是因为\(i=j=1\)的时候答案会被重复统计
这个地方显然是有一些我们很熟悉的东西:\(\varphi\)
线性筛欧拉函数和质数就完事了
CODE
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int N=1e7+10,M=1e6+10;
int n,tot,p[M],phi[N],sum[N];
bool fl[N];
inline void prework()
{
phi[1]=1;
for(int i=2;i<=n;++i)
{
if(!fl[i]) p[++tot]=i,phi[i]=i-1;
for(int j=1;j<=tot&&i*p[j]<=n;++j)
{
fl[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];
return ;
}
signed main()
{
n=read(); prework(); int ans=0;
for(int i=1;i<=tot;++i) ans+=2*sum[n/p[i]]-1;
printf("%lld\n",ans);
return 0;
}
}
signed main(){return yspm::main();}
© 著作权归作者所有
举报
发表评论
0/200