题意：求1--n中满足gcd(x,y)的值为质数的数对(x,y)的数目 （ (x,y)和(y,x)算两个 ）
sol：
设p[i]是一个质数，那么以下两个命题是等价的：
1.gcd(x,y)=1
2.gcd(x*p[i],y*p[i])=p[i]
eg:gcd(36,25)=1，gcd(36*7,25*7)=7
所以对于1--n的所有质数p[i]，求一下1<=x,y<=n/p[i]中所有gcd(x,y)=1的数对的数目即可。
如何求1--r范围内所有互质数对的数目？
考虑欧拉函数φ(x)=1..x中与x互质的数的数目
设x<=y，那么这样就可以求出来了：
for y:= to r do //1不是质数也不是合数，而且1和任意数的gcd都等于1，应该除去
ans+=*phi[y]; //(x,y)和(y,x)算两个
ans++; //这是本题的特殊情况：当x==y时，gcd(y,y)的值也是质数
Solve函数是题解里用的，事先累加了所有2*phi[i]，速度要快一点点
Reference: http://blog.csdn.net/acdreamers/article/details/8542292
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
#define LL long long
#define MMX 10000010
int phi[MMX],p[MMX];
LL psum[MMX];
bool pr[MMX];
LL nm,ret,n; void calc_phi(int n) //求1--n的欧拉函数，phi[i]
{ //psum[n]:sum of phi[1..n]*2
for (int i=;i<=n;i++)
phi[i]=;
phi[]=;
for (int i=;i<=n;i++)
if (!phi[i])
for (int j=i;j<=n;j+=i)
{
if (!phi[j]) phi[j]=j;
phi[j]=phi[j]/i*(i-);
}
psum[]=;
for (int i=;i<=n;i++)
psum[i]=psum[i-]+phi[i]*;
} void isprime(LL n) //求1--n的质数。pr[i]=1 : i is a prime
{
nm=;
memset(pr,true,sizeof(pr));
LL m=sqrt(n+0.5);
pr[]=false;
for (LL i=;i<=m;i++)
if (pr[i])
{
for (LL j=i*i;j<=n;j+=i)
pr[j]=false;
}
for (int i=;i<=n;i++)
if (pr[i])
{
nm++;
p[nm]=i;
}
} LL Solve(int n) //
{
LL ans = ;
for(int i=; i<=nm&&p[i]<=n; i++)
ans += + psum[n/p[i]];
return ans;
} int main()
{
cin>>n;
isprime(n);
calc_phi(n); LL ret=;
for (int i=;i<=nm;i++)
{
int r=n/p[i];
for (int j=;j<=r;j++) //注意1不能包括进去，因为gcd(1,?)恒等于1
ret+=*phi[j];
ret++;
}
cout<<ret<<endl; //cout<<endl<<Solve(n)<<endl;
return ;
}