题目描述
给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.
输入输出格式
输入格式：
一个整数N
输出格式：
答案
输入输出样例
说明
对于样例(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
首先这个题可以用欧拉函数做：
这题嘛，首先我们枚举gcd(x,y)=p的p，那么gcd(x/p,y/p)肯定互质，也就是求在[1,n/p]（向下取整）范围内的欧拉函数的前缀和，再乘2（因为x和y可以交换嘛），在减一，
然后也可以套反演 复杂度差不多是m×sqrt(n)
1 #include <iostream> 2 #include"cmath" 3 #include"cstring" 4 #include"algorithm" 5 #include"stdio.h" 6 using namespace std; 7 typedef long long ll; 8 9 int mu[10000005]; 10 int prime[10000005]; int prime_c; 11 int vis[10000005]; 12 int sum[10000005]; 13 ll ans;int n; 14 15 void Mu() 16 { mu[1]=1; 17 for (int i=2;i<=10000000;i++) 18 { 19 if(!vis[i])mu[i]=-1,prime[++prime_c]=i; 20 for (int j=1;j<=prime_c;j++) 21 { 22 if(1ll*prime[j]*i>1ll*10000000)break; 23 vis[i*prime[j]]=1; 24 if(i%prime[j]==0)break; 25 mu[i*prime[j]]=-mu[i]; 26 } 27 } 28 29 for (int i=1;i<=10000000;i++)sum[i]=sum[i-1]+mu[i]; 30 31 // for (int i=1;i<=100;i++)cout<<mu[i]<<" "; 32 } 33 34 inline void work(int x) 35 { 36 int a=n; a/=x; 37 for (int r,l=1;l<=a;l=r+1) 38 { 39 r=a/(a/l); 40 ans+=1ll*(sum[r]-sum[l-1])*(a/l)*(a/l); 41 } 42 43 44 } 45 46 47 int main() 48 { cin>>n; 49 Mu(); 50 for (int j=1;j<=prime_c;j++) 51 { 52 int now=prime[j];if(now>n)break; 53 work(prime[j]); 54 // cout<<prime[j]<<" "<<ans<<endl; 55 56 } 57 58 cout<<ans; 59 60 61 }