题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2818
题意：给定整数N，求1<=x,y<=n且Gcd(x,y)为素数的数对(x,y)有多少对
思路：先筛出n以内所有的素数顺便筛出欧拉函数，\(gcd(x,y)=k\)等价于\(gcd(\frac{x}{k},\frac{y}{k})=1\)
所以这个问题可以转化为求\(ans=\sum_{i=1}^{tot}\sum_{j=1}^{n/prime[i]}phi[j]\) ，tot为n以内素数个数，
这个公式可以前缀和优化，暴力枚举也能过，而且时间居然只慢了20ms....
求得的结果只是一半的情况,当\(x\not=y,(x,y)\not=(y,x)\),而x=y的情况只有tot种,(2,2),(3,3),(5,5)....(prime[tot],prime[tot]),
所以答案为\(ans*2-tot\)
```c++
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
const double eps=1e-6;
const ll inf=1e18;
const int mod=1e9+7;
const int maxn=1e7+10;
bool b[maxn];
int prime[maxn],tot,n;
ll phi[maxn];
void init(int n){
b[0]=b[1]=phi[1]=1;
for(int i=2;i<=n;i++){
if(!b[i]){
prime[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot;j++){
if(i*prime[j]>n) break;
b[i*prime[j]]=1;
phi[i*prime[j]]=phi[i]*phi[prime[j]];
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
}
}
for(int i=1;i<=n;i++) phi[i]+=phi[i-1];
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
init(n);
ll ans=0,cnt=0;
for(int i=1;i<=tot;i++){
ans+=phi[n/prime[i]];
}
cout<<ans*2-tot<<endl;
return 0;
}
```