http://blog.csdn.net/Clove_unique/article/details/51089272
Key：1、连接平面上某个整点（a,b）到原点的线段上有gcd（a,b）个整点。
2、欧拉函数的性质之一：若(N%a==0 && (N/a)%a==0) 则有:phi(N)=phi(N/a)*a。由此可以线性筛。
3、一个数的所有因子的phi值之和恰好等于这个数本身。
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100000
typedef long long ll;
bool notpri[N+5];
int pri[N+5];
ll phi[N+5];
void shai_eular()//线性筛欧拉函数，顺便处理前缀和
{
notpri[1]=1;
phi[1]=1;
for(int i=2;i<=N;++i){
if(!notpri[i]){
pri[++pri[0]]=i;
phi[i]=(ll)(i-1);
}
for(int j=1;j<=pri[0] && (ll)i*(ll)pri[j]<=(ll)N;++j){
notpri[i*pri[j]]=1;
if(i%pri[j]==0){
phi[i*pri[j]]=phi[i]*(ll)pri[j];
break;
}
phi[i*pri[j]]=phi[i]*(ll)(pri[j]-1);
}
}
for(int i=2;i<=N;++i){
phi[i]+=phi[i-1];
}
}
int n,m;
int main(){
shai_eular();
scanf("%d%d",&n,&m);
if(n>m){
swap(n,m);
}
ll ans=0;
for(int i=1;i<=n;){
int j1=n/(n/i);
int j2=m/(m/i);
int j=min(j1,j2);
ans+=(phi[j]-phi[i-1])*(n/i)*(m/i);
i=j+1;
}
printf("%lld\n",2ll*ans-(ll)n*(ll)m);
return 0;
}