[人工智能]莫比乌斯反演经典例题（1）

链接：P2257 YY的GCD - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题意：给定 n,m，求 ${\sum }_{i=1}^n{\sum }_{j=1}^m[gcd(i,j)==prime]$。
题解：

1. 首先枚举质数可化为 ${\sum }_{d\in prime}^{min(n,m)}{\sum }_{i=1}^{n/d}{\sum }_{j=1}^{m/d}[gcd(i,j)==1]$。
2. 对于后面的式子先来求其函数的反演，
3. 令 $f(n,m,d)={\sum }_{i=1}^n{\sum }_{j=1}^m[gcd(i,j)==d]$，
4. 令 $F(n,m,d)={\sum }_{i=1}^n{\sum }_{j=1}^m[gcd(i,j)==d?k],k为任意数$，可以看出 F 为求 $gcd(i,j)==d$ 倍数的个数，那么 $F(n,m,d)=?\frac{n}{d}??\frac{m}{d}?$ 可以 $O(1)$ 取得。
5. 考虑 $f(a,b,d)$ 与 $F(a,b,d)$ 的关系。实际上，$F(a,b,d)={\sum }_{d|k}^{min(a,b)}f(a,b,k)$，也就是 $gcd$ 为 d 的倍数的个数都可以取。
6. 对 F 进行反演有 $f(a,b,n)={\sum }_{n|d}^{min(a,b)}\mu (\frac{d}{n})F(a,b,d)$。（反演公式 $f(n)={\sum }_{n|d}\mu (\frac{d}{n})F(d)$，不熟的点这里，借用一下别人的博客）
7. 回到 1 ，发现 ${\sum }_{i=1}^{n/d}{\sum }_{j=1}^{m/d}[gcd(i,j)==1]$ 的值为 $f(\frac{n}{d},\frac{m}{d},1)={\sum }_{k=1}^{min(\frac{n}{d},\frac{m}{d})}\mu (k)F(\frac{n}{d},\frac{m}{d},k)={\sum }_{k=1}^{min(\frac{n}{d},\frac{m}{d})}\mu (k)?\frac{n}{k?d}??\frac{m}{k?d}?$ （代入 4）。
8. 答案就是 ${\sum }_{d\in prime}^{min(n,m)}{\sum }_{k=1}^{min(\frac{n}{d},\frac{m}{d})}\mu (k)?\frac{n}{k?d}??\frac{m}{k?d}?$ 。
9. 很明显枚举质数这一位不削掉是不行的，令 $T=k?d$，那么原式子化为 ${\sum }_{d\in prime}^{min(n,m)}{\sum }_{T=1}^{min(n,m)}\mu (\frac{T}{d})?\frac{n}{T}??\frac{m}{T}?$，把第二个累加往外提有 ${\sum }_{T=1}^{min(n,m)}{\sum }_{d\in prime}^{min(n,m)}\mu (\frac{T}{d})?\frac{n}{T}??\frac{m}{T}?$，发现后面的两个除法与 d 无关，往外提为 ${\sum }_{T=1}^{min(n,m)}?\frac{n}{T}??\frac{m}{T}?{\sum }_{d\in prime}^{min(n,m)}\mu (\frac{T}{d})$，观察 ${\sum }_{d\in prime}^{min(n,m)}\mu (\frac{T}{d})$，是可以预处理出前缀和的，具体为一个数的该累加值为其质数的倍数的 $\mu$ 值，按质数的倍数去赋值可以做到 $nlog(n)$ 的预处理，然后在求其前缀和 t。
10. 答案很明显了，通过整除分块求 $?\frac{n}{T}??\frac{m}{T}?$ 的同时乘上那一段的前缀和 $t_r?t_{l?1}$ 。总体复杂度为 $O(nlog(n)+T\sqrt{min(n,m)})$ 。需要注意的是整除分块时两个变量的块并不同步，需要取块长较短的那一个作为右端点去求。

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<functional>
#include<queue>
#include<unordered_map>
#include<map>
#include<set>

using namespace std;
using ll=long long;
using P=pair<int,int>;
const ll inf=1e18;

struct MobiusInversion{
	static constexpr int maxn=1e7+5;
	int cnt;
	vector<int>pri,vs,mu,t;
	MobiusInversion(int x=maxn):pri(x+5),vs(x+5),mu(x+5),t(x+5){
		const int N=x-5;
		cnt=0;
		vs[0]=vs[1]=1,mu[1]=1;
		for(int i=2;i<=N;i++)
		{
			if(!vs[i])
			{
				pri[++cnt]=i,mu[i]=-1;
			}
			for(int j=1;j<=cnt&&i*pri[j]<=N;j++)
			{
				vs[i*pri[j]]=1;
				if(i%pri[j]==0)break;
				mu[i*pri[j]]=-mu[i];
			}
		}
		for(int i=1;i<=cnt;i++)
		{
			for(int j=1;pri[i]*j<=N;j++)
			{
				t[pri[i]*j]+=mu[j];
			}
		}
		for(int i=1;i<=N;i++)t[i]+=t[i-1];
	}

	ll getans(ll a,ll b){
		ll p=min(a,b);
		ll ans=0;
		for(int l=1,r;l<=p;l=r+1)
		{
			r=min(a/(a/l),b/(b/l));
			ans+=(a/l)*(b/l)*(t[r]-t[l-1]);
		}
		return ans;
	};
}tt;

void solve()
{
	ll n,m; cin>>n>>m;
	cout<<tt.getans(n,m)<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t; cin>>t;
	while(t--)solve();
	return 0;
}