Description
设d(x)为x的约数个数，给定N、M，求 
Input
输入文件包含多组测试数据。
第一行，一个整数T，表示测试数据的组数。
接下来的T行，每行两个整数N、M。
Output
T行，每行一个整数，表示你所求的答案。
Sample Input
2
7 4
5 6
Sample Output
110
121
HINT
1<=N, M<=50000
1<=T<=50000
Solution
莫比乌斯反演
但这题更多的是套路
首先，一个神奇的东东：(d(nm)= sum_{i|n}sum_{j|m}[gcd(i,j)=1])
这个东西是个套路，证明的话可以百度，用的确实多
然后就开始推式子
[sum_{i=1}^Nsum_{j=1}^Md(ij)=sum_{i=1}^Nsum_{j=1}^Msum_{k|i}sum_{l|j}[gcd(k,l)=1]
]
[=sum_{i=1}^Nsum_{j=1}^Msum_{k|i}sum_{l|j}sum_{d|gcd(k,l)}mu(d) (sum_{d|n}mu(d)=[n=1])
]
[=sum_{i=1}^Nsum_{j=1}^Msum_{d=1}^{min(N,M)}mu(d)sum_{k|i}sum_{l|j}[d|gcd(k,l)]
]
[=sum_{d=1}^{min(N,M)}mu(d)sum_{i=1}^Nsum_{j=1}^Msum_{k|i}sum_{l|j}[d|gcd(k,l)]
]
[=sum_{d=1}^{min(N,M)}mu(d)sum_{k=1}^Nsum_{l=1}^M[d|gcd(k,l)]lfloor frac{N}{k}
floor lfloor frac{M}{l}
floor
]
[=sum_{d=1}^{min(N,M)}mu(d)sum_{dk=1}^Nsum_{dl=1}^M[d|gcd(dk,dl)]lfloor frac{N}{dk}
floor lfloor frac{M}{dl}
floor
]
[=sum_{d=1}^{min(N,M)}mu(d)sum_{k=1}^{lfloor frac{N}{d}
floor}sum_{l=1}^{lfloor frac{M}{d}
floor}lfloor frac{N}{dk}
floor lfloor frac{M}{dl}
floor
]
[=sum_{d=1}^{min(N,M)}mu(d)(sum_{k=1}^{lfloor frac{N}{d}
floor}lfloor frac{N}{dk}
floor)(sum_{l=1}^{lfloor frac{M}{d}
floor} lfloor frac{M}{dl}
floor)
]
[=sum_{d=1}^{min(N,M)}mu(d) f(lfloor frac{N}{d}
floor) f(lfloor frac{M}{d}
floor) (f(i)=sum_{j=1}^ilfloor frac{i}{j}
floor)
]
于是(mu)用线性筛加前缀和，(f)整除分块预处理
最后求式子再用整除分块
#include<bits/stdc++.h>
#define ll long long
const int MAXN=50000+10;
int T,cnt,prime[MAXN],mu[MAXN],s[MAXN],f[MAXN];
bool vis[MAXN];
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char c=' ')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(c!=' ')putchar(c);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void init()
{
memset(vis,1,sizeof(vis));
vis[0]=vis[1]=0;
mu[1]=1;
for(register int i=2;i<MAXN;++i)
{
if(vis[i])
{
prime[++cnt]=i;
mu[i]=-1;
}
for(register int j=1;j<=cnt&&i*prime[j]<MAXN;++j)
{
vis[i*prime[j]]=0;
if(i%prime[j])mu[i*prime[j]]=-mu[i];
else break;
}
}
for(register int i=1;i<MAXN;++i)s[i]=s[i-1]+mu[i];
for(register int k=1;k<MAXN;++k)
for(register int i=1;;)
{
if(i>k)break;
int j=k/(k/i);
f[k]+=(k/i)*(j-i+1);
i=j+1;
}
}
inline ll solve(int N,int M)
{
ll res=0;
for(register int i=1;;)
{
if(i>min(N,M))break;
int j=min(N/(N/i),M/(M/i));
res+=(ll)f[N/i]*(ll)f[M/i]*(ll)(s[j]-s[i-1]);
i=j+1;
}
return res;
}
int main()
{
read(T);
init();
while(T--)
{
int N,M;
read(N);read(M);
write(solve(N,M),'
');
}
return 0;
}