题意：\(f(n)\)为n的质因子分解中的最大幂指数，求\(\sum_{i=1}^n \sum_{j=1}^m f(gcd(i,j))\)
套路推♂倒
\[\sum_{D=1}^n \sum_{d|D} f(d)\mu(\frac{D}{d}) \frac{n}{D} \frac{m}{D}
\]
\]
这次函数是\(g = (f*\mu )\)，\(f\)显然不是积性函数，但我们照样可以用线性筛
具体做法我晚上回家再补吧草稿纸忘带了...
补：
- \(g(p^a)=p-(p-1)\)
因为卷了\(\mu\)所以只有\(\mu(1)\)和\(\mu(p)\)时有贡献 - 考虑\(g(p_1^{a_1} p_2^{a_2}...p_k^{a_k})\)，相当于选p的集合，每种p只能选一个放到\(\mu\)里，其余部分在\(f\)里
- 所有\(a\)相等时，所有集合的结果都是\(a\)，只有全选时是\(a-1\)，系数\((-1)^k\)，那么结果就是\(-(-1)^k\)咯
- 不相等时，假设最大次数\(a\)有\(b\)个质数，\(a\)出现\(2^b\)此，\(a-1\)出现\(2^{k-b}\)次，正负都抵消了，所以结果为0
线性筛保存最小质因子幂次后的结果和幂次，利用之前的$g$值
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define pii pair<int, int>
#define MP make_pair
#define fir first
#define sec second
typedef long long ll;
const int N=1e7+5;
inline int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
return x*f;
}
int n, m, k;
int notp[N], p[N], g[N]; pii lp[N];
void sieve(int n) {
g[1] = 0;
for(int i=2; i<=n; i++) {
if(!notp[i]) {
p[++p[0]] = i;
g[i] = 1;
lp[i] = MP(i, 1);
}
for(int j=1; j<=p[0] && i*p[j]<=n; j++) {
int t = i*p[j];
notp[t] = 1;
if(i%p[j] == 0) {
lp[t] = MP(lp[i].fir * p[j], lp[i].sec + 1);
int rem = i / lp[i].fir;
if(rem == 1) g[t] = 1;
else g[t] = lp[t].sec == lp[rem].sec ? -g[rem] : 0;
break;
}
lp[t] = MP(p[j], 1);
g[t] = lp[t].sec == lp[i].sec ? -g[i] : 0;
}
}
for(int i=1; i<=n; i++) g[i] += g[i-1];
}
ll cal(int n, int m) {
if(n>m) swap(n, m);
ll ans=0; int r;
for(int i=1; i<=n; i=r+1) {
r = min(n/(n/i), m/(m/i));
ans += (ll) (g[r] - g[i-1]) * (n/i) * (m/i);
}
return ans;
}
int main() {
//freopen("in","r",stdin);
sieve(N-1);
int T=read();
while(T--) {
n=read(); m=read();
printf("%lld\n", cal(n, m));
}
}