题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2818
思路：
题目要求求gcd(x,y)=c,且c为质数的数对(x,y)(x,y<=n)的个数，其实就可以转化为求gcd(x/c,y/c)=1,(x,y<=n/c)的数对的个数，那么就可以用欧拉函数来解决。
（欧拉函数详解请自己GOOGLE,BAIDU）然后先用筛法在求1..n的质数的同时求出每个不大于n的数的欧拉函数，处理成前缀和的形式。（注意(1,1)的数对特殊情况）。
然后枚举每个不大于n的质数C，然后求sigma(1->n/c,f(i))（设欧拉函数为f(x)）,累加起来就是答案。（注意使用无符号64位整数）
代码：
#include <cstdio>
#include <cstring>
#define MAXN 10000001
#define MAXM 1000001
unsigned long long F[MAXN];
bool f[MAXN];
int n;
int m[MAXM];
unsigned long long ans=0;
int main(){
scanf("%d",&n);
memset(f,true,sizeof(f));
for (int i=0;i++<n;){
F[i]=i;
}
F[0]=0;
F[1]=0;
f[1]=false;
m[0]=0;
for (int i=0;i++<n;){
if (f[i]){
m[++m[0]]=i;
F[i]=i-1;
for (int j=i*2;j<=n;j+=i){
F[j]/=i;
F[j]*=i-1;
f[j]=false;
}
}
}
for (int i=0;i++<n;){
F[i]=F[i-1]+F[i];
}
for (int i=0;i++<m[0];){
ans+=F[n/m[i]]*2;
ans++;
}
printf("%lld\n",ans);
return 0;
}
