欧拉函数
玛雅，我应该先看看JZP的论文的……贾志鹏《线性筛法与积性函数》例题一
这题的做法……仔细想下可以得到：$ans=2*\sum_{a=1}^n\sum_{b=1}^m gcd(a,b)-n*m$
那么重点就在于算$\sum_{a=1}^n\sum_{b=1}^m gcd(a,b)$这个东西
copy一下JZP的推导过程：
$$ \begin{aligned} \sum_{a=1}^n \sum_{b=1}^m gcd(a,b) &= \sum_{a=1}^n \sum_{b=1}^m \sum_{d|gcd(a,b)} \varphi(d) \\ &= \sum_{a=1}^n \sum_{b=1}^m \sum_{d|a and d|b} \varphi(d) \\ &= \sum \varphi(d) \sum_{1 \leq a \leq n \&\& d|a} \sum_{1 \leq b \leq m \&\& d|b} 1 \\ &= \sum \varphi(d) ( \sum_{1 \leq a \leq n \&\& d|a} 1) * ( \sum_{1 \leq b \leq m \&\& d|b} 1) \\ &= \sum \varphi(d) \left\lfloor \frac{n}{d} \right\rfloor \left\lfloor \frac{m}{d} \right\rfloor \end{aligned} $$
/**************************************************************
Problem: 2005
User: Tunix
Language: C++
Result: Accepted
Time:40 ms
Memory:2152 kb
****************************************************************/ //BZOJ 2005
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-')r=-;
for(; isdigit(ch);ch=getchar()) v=v*+ch-'';
return r*v;
}
const int N=1e5+,INF=~0u>>;
/*****************template**********************/
int phi[N],prime[N],tot,n,m;
bool check[N];
void getphi(int n){
memset(check,,sizeof check);
phi[]=;
int tot=;
F(i,,n){
if(!check[i]){
prime[++tot]=i;
phi[i]=i-;
}
F(j,,tot){
if(i*prime[j]>n) break;
check[i*prime[j]]=;
if(i%prime[j]==){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-);
}
}
}
int main(){
n=getint(); m=getint();
if (n>m) swap(n,m);
getphi(N-);
LL ans=;
F(i,,n)
ans+=(LL)phi[i]*(n/i)*(m/i);
printf("%lld\n",ans*-(LL)n*m);
return ;
}