[bzoj2818]gcd

https://darkbzoj.cc/problem/2818

https://vjudge.net.cn/contest/649469#problem/Q

给定整数N，求1≤x,y≤N且gcd(x,y)为素数的数对(x,y)有多少对.

N≤10^7

分析：线性筛出不大于N的所有素数，枚举gcd(x,y)(设为p)，问题转化为求(x,y)=p的个数。

设x=x'p, y=y'p，那么有(x,y)=1且1≤x,y≤N/p。

转化为求(x,y)=1且1≤x,y≤n的个数。

求(x,y)=1且1≤x,y≤N的个数：

若x≥y，对于x=1..n，有ϕ(x)个y满足(x,y)=1

若x≤y，对于y=1..n，有ϕ(y)个x满足(x,y)=1

若x=y，只有一种情况：(x=1, y=1)

所以答案为2(ϕ(1)+...+ϕ(n))-1

线性筛筛出欧拉函数、预处理前缀和即可

#include<iostream>
#define int long long
using namespace std;
const int N=10000010;
int n,p[N/10],cnt,phi[N];
typedef long long ll;
ll ans;
bool st[N];
signed main(){
    #ifdef LOCAL
    freopen("1.txt","r",stdin);
    #endif
    #ifndef LOCAL
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    #endif
    cin>>n;
    phi[1]=1;
    for(int i=2,k;i<=n;++i){
        if(!st[i])st[i]=1,p[++cnt]=i,phi[i]=i-1;
        for(int j=1;(k=p[j]*i)<=n;++j){
            st[k]=1;
            if(i%p[j]==0){
                phi[k]=phi[i]*p[j];
                break;
            }
            else phi[k]=phi[i]*(p[j]-1);
        }
    }
    for(int i=2;i<=n;++i)phi[i]+=phi[i-1];
    for(int i=1;i<=cnt;++i){
        int nn=n/p[i];
        ans+=2*phi[nn]-1;
    }
    cout<<ans;
    return 0;
}