题解 P2568 【GCD】
P2568 GCD
题目大意：
给定正整数 \(n\)，求 \(1≤x,y≤n\) 且 \(\gcd(x,y)\) 为素数的数对 \((x,y)\) 有多少对。
solution：
我们已经会求 \(\gcd(x,y)=1\) 的了，那么怎样转化求此题呢？我们给原式变下形：
\[\gcd(x,y)=p \]\[\gcd(x/p,y/p)=1 \]问题转化为求：
\[\sum ^{cnt} _{i=1}\sum ^{n/p_i} _{j=1} \varphi(j) \]后面的可以用前缀和优化掉。
细节处理：
- 注意多算少算的情况。
代码
#include
using namespace std;
typedef long long LL;
const int N=1e7+5;
int n;
int phi[N],pr[N],cnt;
LL pre[N];
inline void xxs(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!phi[i]) pr[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt;j++){
if(i*pr[j]>n) break;
if(i%pr[j]==0){
phi[i*pr[j]]=phi[i]*pr[j];
break;
}
else
phi[i*pr[j]]=phi[i]*(pr[j]-1);
}
}
}
signed main(){
scanf("%d",&n);
xxs();
LL ans=0;
for(int i=1;i<=n;i++)
pre[i]=pre[i-1]+phi[i];
for(int p=1;p<=cnt;p++)
ans+=pre[n/pr[p]];
printf("%lld",ans*2-cnt);
return 0;
}