求1~n内所有数对（x,y）,gcd(x,y)=质数，的对数。
思路：用f[n]求出,含n的对数，最后用sum【n】求和。
对于gcd(x,y)=a(设x<=y,a是质数),则必有gcd(x/a,y/a)=1;所以我只要枚举i（设i=y/a），再枚举所有质数
他们乘积的f[i*a]值包括i的欧拉函数值。时间复杂度（n*质数个数）
#include<iostream>
#include<cstring>
using namespace std;
const int maxx=100010;
int mindiv[maxx+5],phi[maxx+5];
void genphi() //求出1~n内所有数的欧拉函数值
{
for(int i=1; i<=maxx; i++)
{
mindiv[i]=i;
}
for(int i=2; i*i<=maxx; i++) //筛法
{
if(mindiv[i]==i)
{
for(int j=i*i; j<=maxx; j+=i)
{
mindiv[j]=i;
}
}
}
phi[1]=1;
for(int i=2; i<=maxx; i++)
{
phi[i]=phi[i/mindiv[i]];
if((i/mindiv[i])%mindiv[i]==0)
{
phi[i]*=mindiv[i];
}
else
{
phi[i]*=mindiv[i]-1;
}
}
}
int pri[maxx+5];
int nump=0; //素数个数
int pp[maxx+5]; //存素数
void getp()
{
for(int i=2;i<=maxx;i++)
{
while(i<=maxx&&pri[i])i++;
pp[nump++]=i;
for(int j=i*2;j<=maxx;j=j+i)
pri[j]=1;
}
}
long long f[maxx+5];
long long sum[maxx+5];
int main()
{
getp();
genphi();
for(int i=1;i<=maxx;i++) // 枚举每个i，i=y/pp[j]()
{
for(int j=0;j<nump&&i*pp[j]<=maxx;j++) //枚举所有质数
{
if(i!=1) //（a,b）(b,a)算俩次。
f[i*pp[j]]+=phi[i]*2;
else f[i*pp[j]]+=phi[i];
}
}
long long tsum=0;
for(int i=1;i<=maxx;i++)
{
tsum+=f[i];
sum[i]=tsum;
}
int n;
while(cin>>n)
{
cout<<sum[n]<<endl;
} }