莫比乌斯反演
今天是世纪性的一天,因为我又又又又来看数论且弄懂了qwq。
前置知识:交换求和,整除分块(我们需要将式子化为整数分块可以解决的形式)
莫比乌斯函数
->$\mu(d)$
函数构成
-
当$d=1$时,$\mu(d)=1$
-
当$d=\Pi_{i=1}^k$$p_i$,且$p_i$为互异质数时,$\mu(d)=(-1)^k$;
(也就是就是$d$分解质因数后,没有幂次大于2的质因子,此时函数值根据分解的个数决定) -
只要$d$含有任何质因子的幂次大于等于2,则$\mu(d)$$=0$
性质
-
对于任意正整数$n$,$\Sigma_{d|n}$$\Sigma_{d|n}$
-
对于任意正整数$n$,$\Sigma_{d|n}$$\frac{\mu(d)}{n}$$= \frac{\phi(d)}{n}$
code
$O(n)$版本,如果超时请去学杜教筛
void get_mu(int n)
{
mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i]){prim[++cnt]=i;mu[i]=-1;}
for(int j=1;j<=cnt&&prim[j]*i<=n;j++)
{
vis[prim[j]*i]=1;
if(i%prim[j]==0)break;
else mu[i*prim[j]]=-mu[i];
}
}
}
注意
$a|b$的意思为b除以a为整数(b为a的倍数),即a能整除b
莫比乌斯反演
定理
$F(n)$和$f(n)$是定义在非负整数集合上的两个函数,它们之间满足关系
$F(n)=\Sigma_{d|n} f(d)$
那么就有结论
$f(n)=\Sigma_{d|n} \mu(d) F(\frac{n}{d})$
这个定理即为莫比乌斯反演定理.
还有另外一种形式
若
$F(n)=\Sigma_{n|d} f(d)$
则
$f(n)=\Sigma_{n|d}\mu(\frac{d}{n})F(d)$
证明
这里只给出第一种形式的证明,第二种形式同理.
由定理可设
$F(\frac{n}{d})=\Sigma_{i|\frac{n}{d}} f(i)$
$\Sigma_{d|n} \mu(d)F(\frac{n}{d})=\Sigma_{d|n} \mu(d) \Sigma_{i|\frac{n}{d}} f(i)$
$=\Sigma_{di|n}\mu(d) f(i)$//这一步没看懂的去看交换求和,接下来都为交换求和的知识点
$=\Sigma_{i|n}\Sigma_{d|\frac{n}{i}}\mu(d) f(i)$
$=\Sigma_{i|n}f(i)\Sigma_{d|\frac{n}{i}}\mu(d)$
$=\Sigma_{i|n}f(i)\Sigma_{d|\frac{n}{i}}(\mu(d)=[\frac{n}{i}=1])$
//(莫比乌斯函数性质1)只有在$\frac{n}{i}=1$时才有值,其他时候为0;
//因此$n=i$
//故$\Sigma_{i|n}f(i)=f(n)$
$=f(n)$
得证.
例题
P2257 YY的GCD - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
观察定理可知,我们在反演前需要设出$F(n)$与$f(d)$
而对于这种有$gcd$的题目,一般套路为将$f(d)$设为$gcd(i,j)$$=d$的对数,将$F(n)$设为$gcd(i,j)=n$或n的倍数的对数;
(对数为满足条件的$(i,j)$对数)
即有
$f(d)=\Sigma_{i=1}^n\Sigma_{j=1}^m[gcd(i,j)=d]$
$F(n)=\Sigma_{n|d}f(d)=\lfloor \frac{N}{n}\rfloor\lfloor \frac{M}{n}\rfloor$
带入反演公式后有
$f(n)=\Sigma_{n|d}\mu(\frac{d}{n})F(d)$
接下来开始计算答案
$ans=\Sigma_{k\in pr}\Sigma_{i=1}^n\Sigma_{j=1}^m[gcd(i,j)=k]$
$=\Sigma_{k\in pr}f(k)$//反演
$=\Sigma_{k\in pr}\Sigma_{k|d}\mu(\frac{d}{k})F(d)$
为了将$d$消去,设$\frac{d}{k}=v$
$=\Sigma_{k \in pr}\Sigma_{v=1}^{min(\lfloor \frac{n}{k}\rfloor,\lfloor \frac{m}{k}\rfloor)}\mu(v)F(vk)$
$=\Sigma_{k \in pr}\Sigma_{v=1}^{min(\lfloor \frac{n}{k}\rfloor,\lfloor \frac{m}{k}\rfloor)}\mu(v)\lfloor \frac{m}{vk}\rfloor\lfloor \frac{n}{vk}\rfloor$
$=\Sigma_{k \in pr}\Sigma_{vk=1}^{min(n,m)}\mu(v)\lfloor \frac{m}{vk}\rfloor\lfloor \frac{n}{vk}\rfloor$
由于我们需要将式子向整除分块,即形如$\Sigma_{i=1}^n \lfloor\frac{n}{i}\rfloor$的形式
所以我们设$T=vk$
$=\Sigma_{k \in pr}\Sigma_{T=1}^{min(n,m)}\mu(\frac{T}{k})\lfloor \frac{m}{T}\rfloor\lfloor \frac{n}{T}\rfloor$
$=\Sigma_{T=1}^{min(n,m)}\lfloor \frac{m}{T}\rfloor\lfloor \frac{n}{T}\rfloor\Sigma_{k \in pr,k|T}\mu(\frac{T}{k})$
接下来就可以开始运算啦
$g$为$\Sigma_{k \in pr,k|T}\mu(\frac{T}{k})$,即$g[T]$
$sum$为$g$的前缀和,用来计算整除分块.
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e7+10;
ll g[N],sum[N],mu[N];
int T,n,m,pr[N],cnt;
bool st[N];
void get_mu()
{
mu[1]=1;
for(int i=2;i<=N;++i)
{
if(!st[i])mu[i]=-1,pr[++cnt]=i;
for(int j=1;j<=cnt&&i*pr[j]<=N;++j)
{
st[i*pr[j]]=true;
if(i%pr[j]==0)break;
else mu[i*pr[j]]=-mu[i];
}
}
for(int i=1;i<=cnt;++i)
for(int j=1;j*pr[i]<=N;++j)
g[1ll*pr[i]*j]+=mu[j];
for(int i=1;i<=N;++i)sum[i]=sum[i-1]+g[i];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
get_mu();
cin>>T;
while(T--)
{
cin>>n>>m;
if(n>m)swap(n,m);
ll ans=0;
for(int l=1,r;l<=n;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans+=1ll*(m/l)*(n/l)*(sum[r]-sum[l-1]);
}
cout<<ans<<'\n';
}
return 0;
}