给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的 数对(x,y)有多少对.
Input 一个整数N
Output 如题
Sample Input 4
Sample Output 4 Hint hint
对于样例(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
莫比乌斯里面的 u(i) 是 取的素数的组合的前面的正负号 就是 u(1)-u(2)-u(3)-u(5)+u(6)…
重点：gcd(x,y)=k 转化成 gcd(x/k,y//k) == 1 的情况下，这个时候 n/k 是指的全部数量，但是这时候会有 gcd 为1的倍数的情况，所以利用莫比乌斯（容斥来排除）最好用的就是化为1的情况 不能化为1就想办法化1。反正就是对个数进行容斥。
还有就是这题的测评鸡有问题 我暴力求 比网上的优化速度快= =
#include <bits/stdc++.h> using namespace std; const int maxn=1e7+10; bool vis[maxn]; int prime[maxn],mu[maxn]; int cnt; typedef long long ll; void Init(){ int N=maxn; memset(prime,0,sizeof(prime)); memset(mu,0,sizeof(mu)); memset(vis,0,sizeof(vis)); mu[1] = 1; cnt = 0; for(int i=2; i<N; i++){ if(!vis[i]){ prime[cnt++] = i; mu[i] = -1; } for(int j=0; j<cnt&&i*prime[j]<N; j++){ vis[i*prime[j]] = 1; if(i%prime[j]) mu[i*prime[j]] = -mu[i]; else{ mu[i*prime[j]] = 0; break; } } } } ll cal(int x,int n) { ll anss=0; n/=x; for(int i=1;i<=n;i++) anss+=(ll)mu[i]*(n/i)*(n/i); return anss; } int main() { int n; scanf("%d",&n); long long ans=0; Init(); for(int i=0;i<cnt&&prime[i]<=n;i++) { ans+=cal(prime[i],n); } printf("%lld\n",ans ); }网上的优化 就是 如果能整除 sum[i*prime[j]]=mu[i]; 如果不能整除，就是如果可以整除 就是一个整体，不然就只能 sum[i*prime[j]]=mu[i]-sum[i]; 对于那些不能化1的情况 就这么处理
#include <bits/stdc++.h> using namespace std; const int maxn=1e7+10; bool vis[maxn]; int prime[maxn],mu[maxn]; int cnt; typedef long long ll; ll sum[maxn]; void Init(){ int N=maxn; memset(prime,0,sizeof(prime)); memset(mu,0,sizeof(mu)); memset(vis,0,sizeof(vis)); mu[1] = 1; cnt = 0; for(int i=2; i<N; i++){ if(!vis[i]){ prime[cnt++] = i; sum[i]=1; mu[i] = -1; } for(int j=0; j<cnt&&i*prime[j]<N; j++){ vis[i*prime[j]] = 1; if(i%prime[j]) { mu[i*prime[j]] = -mu[i]; sum[i*prime[j]]=mu[i]-sum[i]; } else{ mu[i*prime[j]] = 0; sum[i*prime[j]]=mu[i]; break; } } } } ll work(int n) { ll anss=0; for(int i=2;i<=n;i++) { anss+=(ll)(n/i)*(ll)(n/i)*sum[i]; } return anss; } int main() { int n; long long ans=0; Init(); while(scanf("%d",&n)!=EOF) printf("%lld\n",work(n) ); }