莫比乌斯反演

一.莫比乌斯函数：

1.定义：

μ(d)=⎩⎪⎨⎪⎧​1,(−1)k,0,​d=1d=p1​∗p2​∗...∗pk​,p1​,p2​,...均为互异质数其他情况​

2.性质：

(1) 积性函数，即如果满足 $a$a 和 $b$b 互质，那么就会满足 $f(a\ast b)=f\left(a\right)\ast f\left(b\right)$f(a∗b)=f(a)∗f(b)；

(2) 对任意的正整数 $n$n ,当 $n>1$n>1时，其所有因子的莫比乌斯函数值相加为0，
即：
d∣n∑​μ(d)={1,0,​ n=1 n>1​
证明：
当 $n=1$n=1 时，显然成立；
当 $n>1$n>1 时，
首先，有：
$\mu \left(d\right)\ne 0⟺d=p_1\ast p_2\ast ...\ast p_k$μ(d)​=0⟺d=p1​∗p2​∗...∗pk​
对于 $\mu \left(d\right)=0$μ(d)=0 的因子，我们可以不用考虑，下面仅对 $\mu \left(d\right)\ne 0$μ(d)​=0 的因子讨论。
那么对于一个含有 $r$r 的质因子的因子 $d$d， $\mu \left(d\right)=C_k^r\ast (-1{)}^r$μ(d)=Ckr​∗(−1)r。
所以
$\sum _{d\mid n}\mu \left(d\right)=\sum _{i=0}^k{C}_k^i\ast (-1{)}^i$d∣n∑​μ(d)=i=0∑k​Cki​∗(−1)i
又根据二项式定理：
$(x+y{)}^n=\sum _{i=0}^n{C}_n^i\ast x^i\ast y^{n-i}$(x+y)n=i=0∑n​Cni​∗xi∗yn−i
令 $x=-1,y=1$x=−1,y=1，有
$\sum _{i=0}^k{C}_k^i\ast (-1{)}^i=\sum _{i=0}^k{C}_k^i\ast x^i\ast y^{k-i}=0$i=0∑k​Cki​∗(−1)i=i=0∑k​Cki​∗xi∗yk−i=0
所以，
$\sum _{d\mid n}\mu \left(d\right)=0$d∣n∑​μ(d)=0
即证。

(3) 对任意正整数 $n$n ，有：
$\sum _{d\mid n}\frac{\mu \left(d\right)}{d}=\frac{\phi \left(n\right)}{n}$d∣n∑​dμ(d)​=nφ(n)​

证明：
先证：
$n=\sum _{d\mid n}\phi \left(d\right)$n=d∣n∑​φ(d)

令：
$f\left(n\right)=\sum _{d\mid n}\phi \left(d\right)$f(n)=d∣n∑​φ(d)
有：
$f\left(n\right)\ast f\left(m\right)=\sum _{i\mid n}\phi \left(i\right)\ast \sum _{j\mid m}\phi \left(j\right)$f(n)∗f(m)=i∣n∑​φ(i)∗j∣m∑​φ(j)
$=\sum _{i\mid n}\sum _{j\mid m}\phi \left(i\right)\ast \phi \left(j\right)$=i∣n∑​j∣m∑​φ(i)∗φ(j)
因为欧拉函数为积性函数，所以：
$=\sum _{i\mid n}\sum _{j\mid m}\phi (i\ast j)$=i∣n∑​j∣m∑​φ(i∗j)
$=\sum _{d\mid nm}\phi \left(d\right)$=d∣nm∑​φ(d)
$=f(n\ast m)$=f(n∗m)
所以 $f\left(n\right)$f(n) 是积性函数。
根据唯一分解定理：
$n=p_1^{a_1}\ast p_2^{a_2}\ast ...\ast p_k^{a_k}$n=p1a1​​∗p2a2​​∗...∗pkak​​
所以：
$f\left(n\right)=f(p_1^{a_1}\ast p_2^{a_2}\ast ...\ast p_k^{a_k})=f\left(p_1^{a_1}\right)\ast f\left(p_2^{a_2}\right)\ast ...\ast f\left(p_k^{a_k}\right)$f(n)=f(p1a1​​∗p2a2​​∗...∗pkak​​)=f(p1a1​​)∗f(p2a2​​)∗...∗f(pkak​​)
根据定义，有： $f\left(p^a\right)=\phi \left(1\right)+\phi \left(p\right)+\phi \left(p^2\right)+..+\phi \left(p^a\right)$f(pa)=φ(1)+φ(p)+φ(p2)+..+φ(pa)
由欧拉函数性质，当 $n=p^k$n=pk （ $p$p 为素数）， $\phi \left(n\right)=p^k-p^{k-1}$φ(n)=pk−pk−1，有：
$f\left(p^a\right)=1+(p-1)+(p^2-p)+...+(p^a-p^{a-1})=p^a$f(pa)=1+(p−1)+(p2−p)+...+(pa−pa−1)=pa
所以：
$f\left(n\right)=p_1^{a_1}\ast p_2^{a_2}\ast ...\ast p_k^{a_k}=n$f(n)=p1a1​​∗p2a2​​∗...∗pkak​​=n
所以 $n=\sum _{d\mid n}\phi \left(d\right)$n=d∣n∑​φ(d)
知道这个后，就可以证明性质 $\left(3\right)$(3) 了。
令 $F\left(n\right)=n,f\left(n\right)=\phi \left(n\right)$F(n)=n,f(n)=φ(n)，
所以， $F\left(n\right)=\sum _{d\mid n}f\left(d\right)$F(n)=d∣n∑​f(d)
很明显符合莫比乌斯反演的约数形式，
反演得： $f\left(n\right)=\sum _{d\mid n}\mu \left(d\right)F\left(\frac{n}{d}\right)=\sum _{d\mid n}\mu \left(d\right)\ast \frac{n}{d}$f(n)=d∣n∑​μ(d)F(dn​)=d∣n∑​μ(d)∗dn​
所以： $f\left(n\right)=n\ast \sum _{d\mid n}\frac{\mu \left(d\right)}{d}$f(n)=n∗d∣n∑​dμ(d)​
即： $\sum _{d\mid n}\frac{\mu \left(d\right)}{d}=\frac{\phi \left(n\right)}{n}$d∣n∑​dμ(d)​=nφ(n)​
证毕。

参考博客1
参考博客2

3.线性筛法（基于欧拉筛）

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>prime;
int mob[N];
bool vis[N];
void mobius()
{
    prime.clear();
    memset(vis,0,sizeof(vis));
    mob[1]=1;//莫比乌斯函数第一类情况
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            prime.push_back(i);
            mob[i]=-1;//素数
        }
        for(int j=0;j<prime.size()&&prime[j]*i<N;j++)
        {
            int tmp=i*prime[j];
            vis[tmp]=1;
            if(i%prime[j]==0)
            {
                mob[tmp]=0;//其他情况，因为prime[j]是i的因子，所以k的因子中含有的prime[j]的个数不是1
                break;
            }
            else
               mob[tmp]=-mob[i];//积性函数的性质
        }
    }
}
int main()
{
    mobius();
    for(int i=1;i<=10;i++)
        cout<<mob[i]<<endl;
    return 0;
}

二.莫比乌斯反演：

  当一个函数 $F\left(n\right)$F(n) 很好求时，而其可以写成其 约数 或 倍数 $d$d 的函数 $f\left(d\right)$f(d)， $f\left(d\right)$f(d) 很不好求时，我们可以通过莫比乌斯反演利用 $F\left(n\right)$F(n) 反推 $f\left(d\right)$f(d)，从而快速求解 $f\left(d\right)$f(d)。

$F\left(n\right)$F(n) 和 $f\left(n\right)$f(n) 是定义在非负整数集合上的两个函数。注意 $n$n 和 $d$d 不要弄混。

1.约数形式：

$F\left(n\right)=\sum _{d\mid n}f\left(d\right)⟹f\left(n\right)=\sum _{d\mid n}\mu \left(d\right)\ast F\left(\frac{n}{d}\right)$F(n)=d∣n∑​f(d)⟹f(n)=d∣n∑​μ(d)∗F(dn​)

证明：

${\sum }_{d\mid n}\mu \left(d\right)\ast F\left(\frac{n}{d}\right)={\sum }_{d\mid n}\mu \left(d\right)\ast {\sum }_{k\mid \frac{n}{d}}f\left(k\right)$∑d∣n​μ(d)∗F(dn​)=∑d∣n​μ(d)∗∑k∣dn​​f(k)

$={\sum }_{k\mid n}f\left(k\right){\sum }_{d\mid \frac{n}{k}}\mu \left(d\right)$=∑k∣n​f(k)∑d∣kn​​μ(d) $=f\left(n\right)$=f(n)

$\left(k和d是等价的，原来是一个\mu \right(d\left)对应多个f\right(k),现在是一个f(k\left)对应多个\mu \right(d\left)\right)$(k和d是等价的，原来是一个μ(d)对应多个f(k),现在是一个f(k)对应多个μ(d))

对于 ${\sum }_{d\mid \frac{n}{k}}\mu \left(d\right)$∑d∣kn​​μ(d) ，由莫比乌斯函数的性质，当且仅 $\frac{n}{k}=1$kn​=1 时，其值等于1，否则等于0。

2.倍数形式：

$F\left(n\right)=\sum _{n\mid d}f\left(d\right)⟹f\left(n\right)=\sum _{n\mid d}\mu \left(\frac{d}{n}\right)F\left(d\right)$F(n)=n∣d∑​f(d)⟹f(n)=n∣d∑​μ(nd​)F(d)

证明（同理）：

令 $k=\frac{d}{n}$k=nd​,

${\sum }_{n\mid d}\mu \left(\frac{d}{n}\right)F\left(d\right)$∑n∣d​μ(nd​)F(d)

$={\sum }_{k=1}^{+\infty }\mu \left(k\right)F(n\ast k)$=∑k=1+∞​μ(k)F(n∗k)

$={\sum }_{k=1}^{+\infty }\mu \left(k\right){\sum }_{nk\mid t}f\left(t\right)$=∑k=1+∞​μ(k)∑nk∣t​f(t)

$={\sum }_{n\mid t}f\left(t\right){\sum }_{k\mid \frac{t}{n}}\mu \left(k\right)=f\left(n\right)$=∑n∣t​f(t)∑k∣nt​​μ(k)=f(n)

三.常见应用：

1. $gcd(i,j)$gcd(i,j) 相关问题：

一般先将其转化为求 ${\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)==1]$∑i=1n​∑j=1m​[gcd(i,j)==1] ，然后利用数论分块解决。

求解 ${\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)==1]$∑i=1n​∑j=1m​[gcd(i,j)==1] 的过程：

令 $f\left(d\right)={\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)==d],num=min(n,m)$f(d)=∑i=1n​∑j=1m​[gcd(i,j)==d],num=min(n,m)

令 $F\left(d\right)=f\left(d\right)+f\left(2d\right)+f\left(3d\right)+...+f\left(kd\right)={\sum }_{d\mid n}^{num}f\left(n\right)$F(d)=f(d)+f(2d)+f(3d)+...+f(kd)=∑d∣nnum​f(n)

即 $F\left(d\right)$F(d) 表示 $gcd(i,j)$gcd(i,j) 为 $d$d 的倍数的二元组的个数，显然 $F\left(d\right)=\lfloor \frac{n}{d}\rfloor \ast \lfloor \frac{m}{d}\rfloor$F(d)=⌊dn​⌋∗⌊dm​⌋，容易求得。这样就可以通过 $F\left(d\right)$F(d) 来求 $f\left(d\right)$f(d)了。

由反演公式，得：

$f\left(d\right)={\sum }_{d\mid n}^{num}\mu \left(\frac{n}{d}\right)F\left(n\right)={\sum }_{d\mid n}^{num}\mu \left(\frac{n}{d}\right)\ast \lfloor \frac{n}{n}\rfloor \ast \lfloor \frac{m}{n}\rfloor$f(d)=∑d∣nnum​μ(dn​)F(n)=∑d∣nnum​μ(dn​)∗⌊nn​⌋∗⌊nm​⌋

(向下取整括号中，上面的 $n,m$n,m 是范围，下面的 $n$n 是变量，注意区分)

当 $d=1$d=1时，有：（记住）

$f\left(1\right)={\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)==1]={\sum }_{i=1}^{min(n,m)}\mu \left(i\right)\ast \lfloor \frac{n}{i}\rfloor \ast \lfloor \frac{m}{i}\rfloor$f(1)=∑i=1n​∑j=1m​[gcd(i,j)==1]=∑i=1min(n,m)​μ(i)∗⌊in​⌋∗⌊im​⌋

先预处理出莫比乌斯函数的前缀和，然后用数论分块处理。

各种类型分析及常用方法

<mark>重点【反演解题套路】</mark>：

$\left[gcd\right(i,j)=1]=\sum _{d\mid gcd(i,j)}\mu \left(d\right)=\sum _{d\mid i,d\mid j}\mu \left(d\right)$[gcd(i,j)=1]=d∣gcd(i,j)∑​μ(d)=d∣i,d∣j∑​μ(d)
常见应用过程：

${\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)=1]$∑i=1n​∑j=1m​[gcd(i,j)=1]

$={\sum }_{i=1}^n{\sum }_{j=1}^m{\sum }_{d\mid i,d\mid j}\mu \left(d\right)$=∑i=1n​∑j=1m​∑d∣i,d∣j​μ(d)

$={\sum }_{d=1}^{min(n,m)}\mu \left(d\right)\ast \lfloor \frac{n}{d}\rfloor \ast \lfloor \frac{m}{d}\rfloor$=∑d=1min(n,m)​μ(d)∗⌊dn​⌋∗⌊dm​⌋（改变枚举顺序）

证明：
因为莫比乌斯函数性质 $\left(2\right)$(2): $[n=1]=\sum _{d\mid n}\mu \left(d\right)$[n=1]=d∣n∑​μ(d)
问题：

1.求 ${\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)=d](n\le m)$∑i=1n​∑j=1m​[gcd(i,j)=d](n≤m)

$ANS={\sum }_{i=1}^n{\sum }_{j=1}^m{\sum }_{d\mid gcd(i,j)}\mu \left(d\right)={\sum }_{i=1}^n{\sum }_{j=1}^m{\sum }_{d\mid i,d\mid j}\mu \left(d\right)$ANS=∑i=1n​∑j=1m​∑d∣gcd(i,j)​μ(d)=∑i=1n​∑j=1m​∑d∣i,d∣j​μ(d)

$={\sum }_{d=1}^n\left(\mu \right(d)\ast \lfloor \frac{n}{d}\rfloor \ast \lfloor \frac{m}{d}\rfloor )$=∑d=1n​(μ(d)∗⌊dn​⌋∗⌊dm​⌋)（改变枚举顺序，常用的技巧）

四.例题：

1.hdu1695：

先附上一篇详解和思路
主要是利用莫比乌斯反演的性质来构造函数，同时利用了莫比乌斯反演的第二个函数关系。还有思维的转化。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int mu[N];
bool vis[N];
vector<int>prime;
void mobius()
{
    memset(mu,0,sizeof(mu));
    memset(vis,0,sizeof(vis));
    prime.clear();
    mu[1]=1;
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            prime.push_back(i);
            mu[i]=-1;
        }
        for(int j=0;j<prime.size()&&i*prime[j]<N;j++)
        {
            int tmp=i*prime[j];
            vis[tmp]=1;
            if(i%prime[j]==0)
            {
                mu[tmp]=0;
                break;
            }
            else
                mu[tmp]=-mu[i];
        }
    }
}
int main()
{
    int T,cas=0;
    mobius();
    scanf("%d",&T);
    while(T--)
    {
        int a,b,c,d,k;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        printf("Case %d: ",++cas);
        if(k==0)
        {
            puts("0");
            continue;
        }
        b/=k;
        d/=k;
        long long ans1=0,ans2=0;
        for(int i=1;i<=min(b,d);i++)
            ans1+=(long long)mu[i]*(b/i)*(d/i);
        for(int i=1;i<=min(b,d);i++)
            ans2+=(long long)mu[i]*(min(b,d)/i)*(min(b,d)/i);
        printf("%lld\n",ans1-ans2/2);
    }
    return 0;
}

2.hdu6390：

欧拉函数的性质+莫比乌斯函数性质的运用
已知：

求：

推导：

一直tle,把数据类型改了一下，竟然就过了，玄学。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,m;
ll p,ans;
ll c[N],inv[N];
int prime[N];
bool vis[N];
int mu[N],phi[N];
void mobius_euler()
{
    memset(vis,0,sizeof(vis));
    mu[1]=1;
    phi[1]=1;
    int cnt=0;
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            mu[i]=-1;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<N;j++)
        {
            int tmp=i*prime[j];
            vis[tmp]=1;
            if(i%prime[j]==0)
            {
                mu[tmp]=0;
                phi[tmp]=phi[i]*prime[j];
                break;
            }
            else
            {
                mu[tmp]=-mu[i];
                phi[tmp]=phi[i]*phi[prime[j]];
            }
        }
    }
}
void init()
{
    inv[1]=1;
    for(int i=2;i<=min(n,m);i++)//递推求逆元
        inv[i]=inv[p%i]*(ll)(p-p/i)%p;
    for(int i=1;i<=min(n,m);i++)
        c[i]=(ll)i*inv[phi[i]]%p;
}
ll g(int x,int y)
{
    ll res=0;
    for(int i=1;i<=min(x,y);i++)
        res=(res+(ll)mu[i]*(x/i)*(y/i))%p;
    return res;
}
int main()
{
    int t;
    scanf("%d",&t);
    mobius_euler();
    while(t--)
    {
        scanf("%d%d%lld",&m,&n,&p);
        ans=0;
        init();
        for(int i=1;i<=min(n,m);i++)
            ans=(ans+c[i]*g(m/i,n/i))%p;
        printf("%lld\n",ans);
    }
    return 0;
}

3.bzoj 2301:【莫比乌斯反演+容斥】

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5;
vector<int>prime;
bool vis[N];
int mu[N],sum[N];
void mobius()
{
    memset(vis,0,sizeof(vis));
    memset(mu,0,sizeof(mu));
    memset(sum,0,sizeof(sum));
    prime.clear();
    mu[1]=1;
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            prime.push_back(i);
            mu[i]=-1;
        }
        for(int j=0;j<prime.size()&&i*prime[j]<N;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            else
                mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<N;i++)//莫比乌斯函数前缀和
        sum[i]=sum[i-1]+mu[i];
}
int solve(int n,int m)
{
    int k=min(n,m),res=0;
    for(int l=1,r=1;l<=k;l=r+1)
    {
        r=min(k,min(n/(n/l),m/(m/l)));
        res+=(sum[r]-sum[l-1])*(n/l)*(m/l);
    }
    return res;
}
int main()
{
    int a,b,c,d,k,n;
    mobius();
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        int ans=solve(b/k,d/k)+solve((a-1)/k,(c-1)/k)-solve(b/k,(c-1)/k)-solve((a-1)/k,d/k);//容斥
        printf("%d\n",ans);
    }
    return 0;
}
/* 2 2 5 1 5 1 1 5 1 5 2 */

4.bzoj2005-能量采集：

枚举d.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
bool vis[N];
int mu[N],sum[N];
vector<int>prime;
void mobius()
{
    memset(vis,0,sizeof(vis));
    memset(mu,0,sizeof(mu));
    memset(sum,0,sizeof(sum));
    prime.clear();
    mu[1]=1;
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            prime.push_back(i);
            mu[i]=-1;
        }
        for(int j=0;j<prime.size()&&i*prime[j]<N;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            else
                mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<N;i++)
        sum[i]=sum[i-1]+mu[i];
}
ll solve(int n,int m)
{
    int k=min(n,m);
    int tn=n,tm=m,tk=k;
    ll res=0;
    for(int i=1;i<=k;i++)//gcd==i
    {
        tn=n/i;
        tm=m/i;
        tk=min(tn,tm);
        for(int l=1,r=1;l<=tk;l=r+1)
        {
            r=min(min(tn/(tn/l),tm/(tm/l)),tk);
            res+=((1LL)*(sum[r]-sum[l-1])*(tm/l)*(tn/l))*(1LL)*i;//注意*i,否则，只算了个数。
        }
    }
    return res;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        mobius();
        printf("%lld\n",2*solve(n,m)-(1LL)*n*m);//防爆
    }
    return 0;
}

5.P2257 YY的GCD：

  一开始的做法是直接暴力，先筛出 $[1,1e7]$[1,1e7] 内的所有素数及莫比乌斯函数函数值，然后暴力枚举 $min(n,m)$min(n,m) 内的素数，进行数论分块。只过了一半的测试点就 $t$t 了。

看了题解后发现还可以继续化简：

$ANS={\sum }_{p=1}^{min(n,m)}isprime\left(p\right)\ast {\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)==p]$ANS=∑p=1min(n,m)​isprime(p)∗∑i=1n​∑j=1m​[gcd(i,j)==p]

$={\sum }_{p=1}^{min(n,m)}isprime\left(p\right)\ast {\sum }_{i=1}^{\lfloor \frac{n}{p}\rfloor }{\sum }_{j=1}^{\lfloor \frac{m}{p}\rfloor }\left[gcd\right(i,j)==1]$=∑p=1min(n,m)​isprime(p)∗∑i=1⌊pn​⌋​∑j=1⌊pm​⌋​[gcd(i,j)==1]（我到这步就直接算了）

$={\sum }_{p=1}^{min(n,m)}isprime\left(p\right)\ast {\sum }_{d=1}^{min(\lfloor \frac{n}{p}\rfloor ,\lfloor \frac{m}{p}\rfloor )}\left(\mu \right(d)\ast \lfloor \frac{n}{d\ast p}\rfloor \ast \lfloor \frac{m}{d\ast p}\rfloor )$=∑p=1min(n,m)​isprime(p)∗∑d=1min(⌊pn​⌋,⌊pm​⌋)​(μ(d)∗⌊d∗pn​⌋∗⌊d∗pm​⌋)

令 $T=d\ast p,t=p$T=d∗p,t=p

$={\sum }_{t=1}^{min(n,m)}isprime\left(t\right)\ast {\sum }_{t\mid T}^{min(n,m)}\left(\mu \right(t)\ast \lfloor \frac{n}{T}\rfloor \ast \lfloor \frac{m}{T}\rfloor )$=∑t=1min(n,m)​isprime(t)∗∑t∣Tmin(n,m)​(μ(t)∗⌊Tn​⌋∗⌊Tm​⌋)

$={\sum }_{T=1}^{min(n,m)}\lfloor \frac{n}{T}\rfloor \ast \lfloor \frac{m}{T}\rfloor \ast {\sum }_{t\mid T,t\in prime}\mu \left(\frac{T}{t}\right)$=∑T=1min(n,m)​⌊Tn​⌋∗⌊Tm​⌋∗∑t∣T,t∈prime​μ(tT​)

到此化简结束。
前半部分可以通过数论分块处理，后面可以在求莫比乌斯反演的时候预处理。
AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+5;
vector<int> prime;
bool vis[N];
int mu[N];
ll sum[N],T[N];
void euler()
{
    mu[1]=1;
    for(int i=2;i<=N-5;i++)
    {
        if(!vis[i])
        {
            prime.push_back(i);
            mu[i]=-1;
        }
        for(int j=0;j<prime.size()&&i*prime[j]<=N-5;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            else
                mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=0;i<prime.size();i++)
    {
        for(int j=1;j*prime[i]<=N-5;j++)
            T[j*prime[i]]+=mu[j];
    }
    for(int i=1;i<=N-5;i++)
        sum[i]=sum[i-1]+T[i];
}
ll solve(int n,int m)
{
    ll res=0;
    int minn=min(n,m);
    for(int l=1,r=1;l<=minn;l=r+1)
    {
        r=min(min(m/(m/l),n/(n/l)),minn);//cout<<"r= "<<r<<endl;
        res+=1LL*(sum[r]-sum[l-1])*(n/l)*(m/l);
    }
    return res;
}
int main()
{
    int t,n,m;
    euler();//cout<<prime.size()<<endl;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        ll ans=solve(n,m);
        printf("%lld\n",ans);
    }
    return 0;
}