前置：整除分块
- 主要形式就是：
\[\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor\]
这个式子正常是 有许多的 。我们就可以根据它们的分布情况进行计算。
可以发现，对于每个相同值的一块，最后一个数是 反演了。
定理
定义 反演。
由于只有在 \(gcd(i,j)=1\) 时才有贡献，那么我们就可以根据第一个莫比乌斯函数的性质（忘了往上翻）把最后一个 \(gcd(i,j)=1\) 进行转换，变为：
\[\sum_{k\in prime}\sum_{i=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{k}\right \rfloor}\sum_{d|gcd(i,j)}\mu(d)\]
那么在这里， \(d\) 一定是 \(gcd(i,j)\) 的倍数，所以我们就可以继续化简，在 \(i\)，\(j\) 的极限值上同时除以一个 \(d\) ，直接乘在式子里即可，然后枚举 \(d\)。得到：
\[\sum_{k\in prime}\sum_{d=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\mu(d)\times \left \lfloor \frac{m}{kd} \right \rfloor\times \left \lfloor \frac{n}{kd} \right \rfloor\]
这样的时间复杂度还是不对的，因为最大的 \(n,m\) 是 \(10^7\)，所以我们就可以（不得不）继续化简。
设 \(tmp=kd\) ，那么原式子就变成了：
\[\sum_{k\in prime}\sum_{d=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\mu(d)\times \left \lfloor \frac{m}{tmp} \right \rfloor\times \left \lfloor \frac{n}{tmp} \right \rfloor\]
我们再对这个式子化简，把 \(tmp\) 提前枚举，那么我们就得到了最终的式子：
\[\sum_{tmp=1}^{n}\times \left \lfloor \frac{m}{tmp} \right \rfloor\times \left \lfloor \frac{n}{tmp} \right \rfloor\times (\sum_{k|tmp\ \&\&\ k \in prime}\mu(\frac{tmp}{k}))\]
最后这个式子我们可以在线性筛的时候用迪利克雷前缀和来搞一个前缀和，然后在下边只需要用整除分块的思想枚举 \(tmp\) ，每一块的和就能求出来了。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7+10;
int mu[maxn],noprime[maxn],prime[maxn];
int sum[maxn],f[maxn];
int n;
void xxs(){
mu[1] = 1;
noprime[1] = 1;
for(int i = 2;i <= 10000000;++i){
if(!noprime[i]){
prime[++prime[0]] = i;
mu[i] = -1;
}
for(int j = 1,k;j <= prime[0] && (k = i * prime[j]) <= 10000000;++j){
noprime[k] = 1;
if(i % prime[j] == 0)break;
else mu[k] = -mu[i];
}
}
for(int i = 1;i <= prime[0];++i){
for(int j = 1;j * prime[i] <= 10000000;++j){
f[j * prime[i]] += mu[j];
}
}
for(int i = 1;i <= 10000000;++i){
sum[i] = sum[i-1] + f[i];
}
}
#define ll long long
int main(){
xxs();
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
if(n > m)swap(n,m);
long long ans = 0;
for(int l = 1,r = 0;l <= n;l = r + 1){
r = min(n / (n / l),m / (m / l));
ans += (ll)(sum[r] - sum[l-1]) * (ll)(n / l) * (ll)(m / l);
}
printf("%lld\n",ans);
}
return 0;
}
莫比乌斯反演的一些知识就到这里，其考察的一些题都是一些推柿子，所以需要慢慢钻研。筛法以后可能会更新（那得看我会不会退役），持续更新（咕咕咕）。
\(Never\ Give\ Up\)