题意：
对于正整数n，定义$f(n)$为$n$所含质因子的最大幂指数。例如$f(1960)=f(2^3 * 5^1 * 7^2)=3$，$f(10007)=1$，$f(1)=0$。
给定正整数$a,b$，求
$$\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}f(gcd(i,j))$$
多组数据，$T\leq 10000$
$1\leq a,b\leq 10^7$
题解：
还是莫比乌斯反演，设$a<b$：
$$\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}f(gcd(i,j))$$
$$=\sum\limits_{d=1}^{a}f(d)\sum\limits_{k=1}^{\lfloor\frac{a}{d}\rfloor}\mu(k)\lfloor\frac{a}{kd}\rfloor\lfloor\frac{b}{kd}\rfloor$$
$$=\sum\limits_{i=1}^{a}\lfloor\frac{a}{i}\rfloor\lfloor\frac{b}{i}\rfloor\sum\limits_{d|i}f(d)\mu(\frac{i}{d})$$
设$g(n)=\sum\limits_{d|n}f(d)\mu(\frac{n}{d})$，分析这个函数的性质；
先将$n$质因数分解，$n=\prod\limits_{i=1}^{l}p_i^{a_i}$，设$k=max\{a_i\}$；
显然当且仅当$\frac{n}{d}$每个质因子次数都不超过1时$\mu(\frac{n}{d})$才非零，所以$f(d)$的值只能取到$k$或者$k-1$；
那么可以将所有$a_i$分成两个集合，$A$集合表示取到$k$的，$B$集合表示小于$k$的，显然$g$的取值由$A$中的元素决定；考虑$d$减少了哪些质因数的次数，如果有$A$集合中的元素被选到，则剩下的在$B$集合中的选择奇偶可能性相同；
根据$\mu$的定义可以知道，奇数会产生1的贡献，偶数则会产生-1的贡献，则全部的贡献加起来就为0；
如果不选$A$中的元素，则对B也类似分成两半来讨论，最终还是会得到0；
因此只有$a_i$全相等的情况才会产生非零的答案；
在里面任意选奇数或偶数个方案数依然相等，加起来贡献为0，但是特殊情况是全选时，此时$f$的值为$k-1$（其他情况为$k$），因此要多减去一个1；
所以此时$g(n)=(-1)^{l+1}$，其他时候$g(n)$均为0；
记录一下每个数的最小素因子次数和除掉最小素因子的上一个数，就可以线性筛预处理了；
剩下的数论分块前缀和啥的就是常规操作了吧……
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define inf 2147483647
#define eps 1e-9
using namespace std;
typedef long long ll;
int T,n,m,pri=,p[],g[],t[],las[];
bool isp[];
void _(){
for(int i=;i<=;i++){
if(!isp[i]){
p[++pri]=i;
t[i]=las[i]=g[i]=;
}
for(int j=;j<=pri&&i*p[j]<=;j++){
isp[i*p[j]]=true;
if(i%p[j]==){
las[i*p[j]]=las[i];
t[i*p[j]]=t[i]+;
if(las[i]==)g[i*p[j]]=;
else if(t[las[i]]==t[i]+)g[i*p[j]]=-g[las[i]];
break;
}
las[i*p[j]]=i;
t[i*p[j]]=;
if(t[i]==)g[i*p[j]]=-g[i];
}
}
for(int i=;i<=;i++)g[i]+=g[i-];
}
ll calc(int n,int m){
ll ret=;
for(int i=,las=;i<=n;i=las+){
las=min(n/(n/i),m/(m/i));
ret+=(ll)(g[las]-g[i-])*(n/i)*(m/i);
}
return ret;
}
int main(){
_();
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
if(n>m)swap(n,m);
printf("%lld\n",calc(n,m));
}
return ;
}