最大公约数（gcd为素数的数对个数

# 题意

给定一个数n，求出 1 ≤ x，y ≤ n ，gcd(x,y)为质数

数据范围：

1 ≤ n ≤ 10⁷

# 题解

gcd(x,y)=p

=>gcd(x/p,y/p)=1

x'=x/p,y'=y/p

即转化为了在1 ≤ x'，y' ≤ n/p 中互质的个数和

x和y代表不同，所以对于(x₁,y₁),(x₂,y₂),x₁=y₂,y₁=x₂,是不同的。

预处理欧拉函数的前缀和，对于每个质数判断即可

特别的是当(x,y)=(1,1)的时候只有1个所以特殊判断

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N=1e7+10;
 5 int primes[N],cnt;
 6 bool st[N];
 7 int phi[N];
 8 ll sum[N];
 9 void get_primes(int n){
10     for(int i=2;i<=n;i++){
11         if(!st[i]){
12             primes[cnt++]=i;
13             phi[i]=i-1;
14         }
15         for(int j=0;primes[j] <= n/i;j++){
16             st[primes[j]*i]=true;
17             if(i%primes[j]==0){
18                 phi[i*primes[j]]=primes[j]*phi[i];
19                 break;
20             }
21             phi[i*primes[j]]=phi[i]*(primes[j]-1);
22         }
23     }
24     for(int i=1;i<=n;i++)
25         sum[i]+=sum[i-1]+phi[i];
26 }
27 
28 int main(){
29     int n;
30     cin>>n;
31     get_primes(n);
32     ll ans=0;
33     for(int i=0;i<cnt;i++){
34         int p=primes[i];
35         ans += sum[n/p]*2+1;
36     }
37     cout<<ans<<endl;
38     return 0;
39 }