GCD 题解

· · 题解

B

题意

给定正整数 n，求 1 \le x,y \le n 且 \gcd(x,y) 是素数的数对 (x,y) 的数量。

思路

脑抽数论题。

形象化题意：

\sum_{p\in prime}^{} \sum_{x=1}^{n} \sum_{y=1}^{n} \left [ \gcd(x,y)==p \right ]

不难发现，\gcd(x,y)==p 和 \gcd(\frac{x}{p} ,\frac{y}{p} )==1 是等价的。

于是可以将式子转化成

\sum_{p\in prime}^{} \sum_{x=1}^{\frac{n}{p}} \sum_{y=1}^{\frac{n}{p}} \left [ \gcd(x ,y )==1 \right ]

不难发现，这个式子具有对称性，即很多计算重复了两次，我们可以简化一下式子：

\sum_{p\in prime}^{} \sum_{x=1}^{\frac{n}{p}} (2\sum_{y=1}^{x} \left [ \gcd(x ,y )==1 \right ])-1

-1 是因为 x=y 这个情况，这个只应该被计算一次，而我们计算了两次，所以要减去一次。

而这个式子 \sum_{y=1}^{x} \left [ \gcd(x ,y )==1 \right ] 就是欧拉函数。即 \sum_{y=1}^{x} \left [ \gcd(x ,y )==1 \right ]=\varphi (i)

式子又可以转化为：

\sum_{p\in prime}^{} 2(\sum_{x=1}^{\frac{n}{p}} \varphi (i))-1

最后要求的式子便为：

\sum_{p\in prime}^{} 2(\sum_{x=1}^{\frac{n}{p}} \varphi (i))-1

其中，欧拉函数可以利用前缀和优化思想 \Theta(1) 直接求出。

而质数可以用欧拉筛线性求出。

(不会欧拉筛的请看这里，欧拉函数的请看这里这里)

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>

using namespace std;

#define int long long
#define ll long long
#define Endl cout<<endl;
#define xy cout<<"xy";
#define yx cout<<"yx";
#define pii pair<int,int>
#define ls(rt) tr[rt].ch[0]
#define rs(rt) tr[rt].ch[1]

const int N=1e7+10;//注意修改
const int mod=1e9+7;
const int M=2e5+10;
int prime[N],st[N],n,cnt=0,phi[N],s[N],ans;
void Pr(){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(st[i]==0){
            cnt++;
            prime[cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&prime[j]*i<=n;j++){
            st[prime[j]*i]=1;
            if(i%prime[j]==0) {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }
}

signed main(){
    cin>>n;
    Pr();
    for(int i=1;i<=n;i++) s[i]=s[i-1]+phi[i];
    for(int i=1;i<=cnt;i++) ans+=2*s[n/prime[i]]-1;
    cout<<ans;
    return 0;
}

/*

 */