P2568 GCD
题目描述
给定正整数 n,求 1\le x,y\le n 且 \gcd(x,y) 为素数的数对 (x,y) 有多少对。
Solution
假设 \gcd(x,y)=p ,p 为素数。
那么有 x=a\times p ,y=b\times p ,且 a\bot b
所以我们只用枚举每个素数,看有多少 (a,b) 数对满足 a\bot b 即可
我们不妨设 a\leq b \leq \frac{n}{p} (等号只有在 a=1,b=1 时对答案有贡献),这样最后只用在答案上乘以 2 即可
对于每一个 b ,我们知道一共有 \phi(b) 个数与 b 互质。
于是对于每个质数 p ,贡献出的答案就是 \frac{n}{\phi(p)}
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7+10;
int vis[maxn];
int prime[maxn];
int phi[maxn];
long long sum[maxn];
void get_phi(){
phi[1]=1;
int cnt=0;
for(int i=2;i<maxn;i++) {
if(!vis[i]) {
vis[i]=i;
prime[cnt++]=i;
phi[i]=i-1;
}
for(int j=0;j<cnt;j++) {
if(i*prime[j] > maxn) break;
vis[i*prime[j]] = prime[j];
if(i%prime[j]==0){
phi[i*prime[j]] = phi[i]*prime[j];
break;
}
phi[i*prime[j]] = phi[i]*phi[prime[j]];
}
}
}
int main(){
get_phi();
int n;
scanf("%d",&n);
long long ans = 0 ;
for(int i=1;i<=n;++i)
sum[i] += sum[i-1] + 1ll*phi[i];
for(int i=0;prime[i]<=n;++i)
ans += 2ll*sum[n/prime[i]]-1;
printf("%lld\n",ans);
return 0;
}
0 条评论