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