本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-30 16:30:21

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 ]=\arphi (i)$

式子又可以转化为： $$\sum_{p\in prime}^{} 2(\sum_{x=1}^{\frac{n}{p}} \arphi (i))-1 $$

最后要求的式子便为：

$$\sum_{p\in prime}^{} 2(\sum_{x=1}^{\frac{n}{p}} \arphi (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;
}


\/*

 *\/