【题意】2154: Crash的数字表格 莫比乌斯反演，多组询问，T<=10000。
【算法】数论（莫比乌斯反演）
【题解】由上一题，
$ans=\sum_{g\leq min(n,m)}g\sum_{d\leq min(n/g,m/g)}\mu (d)*d^2*sum(n/gd,m/gd)$
令T=gd
$ans=\sum_{T\leq min(n,m)}sum(n/T,m/T)*T\sum_{d|T}\mu (d)*d$
后面部分由积性函数的乘积和约数和也是积性函数可以线性筛得出。
当i%prime[j]=0时，相对于i多出来的因子必然由重复因子即μ(d)=0，故无视即可。
复杂度O(n+T√n)。
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e7,maxn=1e7+,MOD=1e8+;//
int s[maxn],sum[maxn],prime[maxn],tot,n,m;
bool mark[maxn];
int SUM(int x,int y){return 1ll*(1ll*x*(x+)/%MOD)*(1ll*y*(y+)/%MOD)%MOD;}
int main(){
s[]=;sum[]=;
for(int i=;i<=N;i++){
if(!mark[i]){s[prime[++tot]=i]=(-i+MOD)%MOD;}
for(int j=;j<=tot&&i*prime[j]<=N;j++){
mark[i*prime[j]]=;
if(i%prime[j]==){s[i*prime[j]]=s[i];break;}
s[i*prime[j]]=1ll*s[i]*s[prime[j]]%MOD;
}
sum[i]=(1ll*i*s[i]+sum[i-])%MOD;
}
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
int z=min(n,m),pos=,ans=;
for(int i=;i<=z;i=pos+){
pos=min(n/(n/i),m/(m/i));
ans=(ans+1ll*(sum[pos]-sum[i-]+MOD)*SUM(n/i,m/i)%MOD)%MOD;
}
printf("%d\n",ans);
}
return ;
}