【OI】莫比乌斯函数
|
115
|
OI

定义

本文中默认将正整数 $n$ 分解质因数得到 $n=\prod_{i=1}^{m} p_i^{c_i}$。

莫比乌斯函数的定义为：

μ(n)={1n=10∃i,ci≥2(−1)m∀i,ci=1\mu(n)=\begin{cases} 1 & n=1 \\ 0 & \exists i,c_i\ge 2 \\ (-1)^m & \forall i,c_i=1 \end{cases}

翻译成中文就是：

  • 当 $n=1$ 时，$\mu(n)=1$
  • 当 $n$ 存在次数大于等于 $2$ 的质因子时，$\mu(n)=0$
  • 否则当 $n$ 的所有质因子次数都为 $1$ 时，$\mu(n)=(-1)^m$。

性质

性质1

$\mu$ 为积性函数，即若 $(a,b)=1$，则 $\mu(ab)=\mu(a)\mu(b)$。

最暴力的证法就是把 $a,b$ 各分三类，分讨可证。总之非常显然。

性质2

∑d|nμ(d)=[n=1]\sum_{d|n}\mu(d)=[n=1]

证明老师上课好像没讲，就参考 OI-wiki 的证法了：

设 $n’=\prod_{i=1}^{m} p_i$，则：

∑d|nμ(d)=∑d|n′μ(d)=∑i=0m(mi)(−1)i=(1+(−1))m=[m=0]=[n=1]\sum_{d|n}\mu(d)=\sum_{d|n’}\mu(d)=\sum_{i=0}^{m}\binom{m}{i}(-1)^i=(1+(-1))^m=[m=0]=[n=1]

基于这个性质，我们可以将 $[(i,j)=1]$ 进行转化：

[(i,j)=1]=∑x|(i,j)μ(d)=∑d|i,d|jμ(d)[(i,j)=1]=\sum_{x|(i,j)}\mu(d)=\sum_{d|i,d|j}\mu(d)

线性求 $\mu$

与 $\varphi$ 求法相似，基于线性筛可以 $O(n)$ 求出。

C++
const int N=1e6;
vi prm,v(N+1),mu(N+1);
mu[1]=1;
for(int i=2;i<=N;i++){
    if(!v[i])prm.eb(i),v[i]=i,mu[i]=-1;
    for(auto p:prm){
        if(i*p>N||v[i]<p)break;
        v[i*p]=p;
        mu[i*p]=(mu[i]==0||i%p==0?0:-mu[i]);
    }
}

莫比乌斯反演

木莫木反（确信

莫比乌斯反演如下：

f(n)=∑d|ng(d)⟺g(n)=∑n|dμ(dn)f(d)f(n)=\sum_{d|n}g(d)\Longleftrightarrow g(n)=\sum_{n|d}\mu\left(\frac{d}{n}\right)f(d)

证明如下：

∑d|nμ(nd)f(d)=∑d|nμ(nd)∑k|dg(k)=∑k|ng(k)∑k|d|nμ(nd)=∑k|ng(k)∑k|nd|nμ(nd)=∑k|ng(k)∑k|x|nμ(x)=∑k|ng(k)∑x|nkμ(x)=∑k|ng(k)[nk=1]=g(n).\begin{aligned} \sum_{d \mid n} \mu\left(\frac{n}{d}\right) f(d) & =\sum_{d \mid n} \mu\left(\frac{n}{d}\right) \sum_{k \mid d} g(k) \\ & =\sum_{k \mid n} g(k) \sum_{k|d|n}\mu\left(\frac{n}{d}\right) \\ & =\sum_{k \mid n} g(k) \sum_{k|\frac{n}{d}|n}\mu\left(\frac{n}{d}\right) \\ & =\sum_{k \mid n} g(k) \sum_{k|x|n}\mu(x) \\ & =\sum_{k \mid n} g(k) \sum_{x|\frac{n}{k}}\mu(x) \\ & =\sum_{k \mid n} g(k)\left[\frac{n}{k}=1\right] \\ & =g(n) . \end{aligned}

其中倒数第三行到倒数第二行利用上述的性质2进行转化。

例题

例题1(P3704)

题目大意：

$T(1\le T\le 3000)$ 组数据，每次给定 $n,m(1\le n,m\le 1\times 10^6)$，求：

∏i=1n∏j=1mf(gcd⁡(i,j))\prod_{i=1}^{n}\prod_{j=1}^{m}f(\gcd(i,j))

其中 $f(x)$ 表示菲波那切数列第 $i$ 项。

这道题用莫比乌斯函数直接推式子，不妨设 $n\le m$。

首先容易想到，可以将原问题转化为计算 $f(x)(x\le m)$ 对于答案的贡献，即：

∏i=1n∏j=1mf((i,j))=∏i=1n∏j=1m∏d|i,d|jf(d)=∏d=1n∏i=1n∏j=1mf(d)[(i,j)=d]=∏d=1n∏i=1⌊nd⌋∏j=1⌊md⌋f(d)[(i,j)=1]\begin{aligned} \prod_{i=1}^{n}\prod_{j=1}^{m}f((i,j)) & =\prod_{i=1}^{n}\prod_{j=1}^{m}\prod_{d|i,d|j} f(d)\\ &=\prod_{d=1}^n \prod_{i=1}^n \prod_{j=1}^m f(d)^{[(i,j)=d]}\\ &=\prod_{d=1}^n \prod_{i=1}^{\lfloor\frac{n}{d}\rfloor} \prod_{j=1}^{\lfloor\frac{m}{d}\rfloor} f(d)^{[(i,j)=1]}\\ \end{aligned}

$f(d)$ 的指数可以通过性质2得到：

∏i=1n∏j=1mf((i,j))=∏d=1n∏i=1⌊nd⌋∏j=1⌊md⌋f(d)∑x|(i,j)μ(x)=∏d=1n∏i=1⌊nd⌋∏j=1⌊md⌋f(d)∑x|i,x|jμ(x)\begin{aligned} \prod_{i=1}^{n}\prod_{j=1}^{m}f((i,j)) &=\prod_{d=1}^n \prod_{i=1}^{\lfloor\frac{n}{d}\rfloor} \prod_{j=1}^{\lfloor\frac{m}{d}\rfloor} f(d)^{\sum\limits_{x|(i,j)}\mu(x)}\\ &=\prod_{d=1}^n \prod_{i=1}^{\lfloor\frac{n}{d}\rfloor} \prod_{j=1}^{\lfloor\frac{m}{d}\rfloor} f(d)^{\sum\limits_{x|i,x|j}\mu(x)}\\ \end{aligned}

把指数写成底数的乘积：

∏i=1n∏j=1mf((i,j))=∏d=1n∏i=1⌊nd⌋∏j=1⌊md⌋∏x|i,x|jf(d)μ(x)=∏d=1n∏x=1n∏i=1⌊ndx⌋∏j=1⌊mdx⌋f(d)μ(x)=∏d=1n∏x=1nf(d)μ(x)⌊ndx⌋⌊mdx⌋=∏d=1n∏x=1⌊nd⌋f(d)μ(x)⌊ndx⌋⌊mdx⌋\begin{aligned} \prod_{i=1}^{n}\prod_{j=1}^{m}f((i,j)) &=\prod_{d=1}^n \prod_{i=1}^{\lfloor\frac{n}{d}\rfloor} \prod_{j=1}^{\lfloor\frac{m}{d}\rfloor} \prod_{x|i,x|j} f(d)^{\mu(x)}\\ &=\prod_{d=1}^n \prod_{x=1}^{n} \prod_{i=1}^{\lfloor\frac{n}{dx}\rfloor} \prod_{j=1}^{\lfloor\frac{m}{dx}\rfloor} f(d)^{\mu(x)}\\ &=\prod_{d=1}^n \prod_{x=1}^{n} f(d)^{\mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor}\\ &=\prod_{d=1}^n \prod_{x=1}^{\lfloor\frac{n}{d}\rfloor} f(d)^{\mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor} \end{aligned}

设 $t=dx$，则：

∏i=1n∏j=1mf((i,j))=∏t=1n∏d|tf(d)μ(td)⌊ndx⌋⌊mdx⌋\begin{aligned} \prod_{i=1}^{n}\prod_{j=1}^{m}f((i,j)) &=\prod_{t=1}^{n}\prod_{d|t}f(d)^{\mu(\frac{t}{d})\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor} \end{aligned}

其中 $\prod_{d|t}f(d)^{\mu(\frac{t}{d})}$ 的值仅与 $t$ 有关，记为 $G(t)$。则：

∏i=1n∏j=1mf((i,j))=∏t=1nG(t)⌊ndx⌋⌊mdx⌋\begin{aligned} \prod_{i=1}^{n}\prod_{j=1}^{m}f((i,j)) &=\prod_{t=1}^{n}G(t)^{\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor}\\ \end{aligned}

$f(x),\mu(x)$ 都可以线性预处理出，$G(x)$ 可以 $O(n)$ 枚举每个数，把它的倍数都乘以对应的值即可 $O(n\log n)$ 预处理。最终每次询问时，使用数论分块进行计算即可。

代码
C++
#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cerr<<#x<<':'<<(x)<<' '
#define dbe(x) cerr<<#x<<':'<<(x)<<endl
#define eb emplace_back
#define ep emplace
#define endl '\n'
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using tp=tuple<int,int>;
const int N=1e6;
template<int Mod>struct modint{
    int x;
    modint():x(0){}
    modint(int x):x(x<0?x+Mod:x){}
    modint& operator=(int y){return x=(y<0?y+Mod:y),*this;}
    modint operator+(const modint& y){return x+y.x>=Mod?x+y.x-Mod:x+y.x;}
    modint operator-(const modint& y){return x-y.x<0?x-y.x+Mod:x-y.x;}
    modint operator*(const modint& y){return (ll)x*y.x%Mod;}
    modint operator^(int y)const{
        if(y>=Mod-1||y<=1-Mod)y%=Mod-1;
        if(y<0)y+=Mod-1;
        modint ans=1,a=*this;
        while(y){
            if(y&1)ans=ans*a;
            a=a*a;
            y>>=1;
        }
        return ans;
    }
    modint operator/(const modint& y){return *this*(y^(Mod-2));}
    modint& operator+=(const modint& y){return *this=*this+y;}
    modint& operator-=(const modint& y){return *this=*this-y;}
    modint& operator*=(const modint& y){return *this=*this*y;}
    modint& operator^=(int y){return *this=*this^y;}
    modint& operator/=(const modint& y){return *this=*this/y;}
    bool operator==(const modint& y){return x==y.x;}
    bool operator!=(const modint& y){return x!=y.x;}
    friend istream& operator>>(istream& is,modint& y){return is>>y.x;}
    friend ostream& operator<<(ostream& os,const modint& y){return os<<y.x;}
};
const int P=1e9+7;
using mint=modint<P>;
using vm=vector<mint>;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    vm fib(N+1);fib[1]=1;
    for(int i=2;i<=N;i++)fib[i]=fib[i-1]+fib[i-2];
    vi prm,v(N+1),mu(N+1);{
        mu[1]=1;
        for(int i=2;i<=N;i++){
            if(!v[i])prm.eb(i),v[i]=i,mu[i]=-1;
            for(auto p:prm){
                if(i*p>N||v[i]<p)break;
                v[i*p]=p;
                mu[i*p]=(mu[i]==0||i%p==0?0:-mu[i]);
            }
        }
    }
    vm G(N+1,1);{
        G[1]=1;
        for(int d=1;d<=N;d++){
            for(int i=1;d*i<=N;i++){
                G[d*i]*=(fib[d]^mu[i]);
            }
        }
    }
    vm qzG(N+1);{
        qzG[0]=1;
        for(int i=1;i<=N;i++){
            qzG[i]=qzG[i-1]*G[i];
        }
    }
    
    int T;
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        if(n>m)swap(n,m);
        mint ans=1;
        for(int l=1,r;l<=n;l=r+1){
            r=min(n/(n/l),m/(m/l));
            int o=ll(n/l)*(m/l)%(P-1);
            ans*=(qzG[r]/qzG[l-1])^o;
        }
        cout<<ans<<endl;
    }
    return 0;
}

例题2

还没做。

C++OI数学算法

评论

  1. Lawrence003
    2 月前
    2026-1-25 19:51:19

    什么雷霆题目

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇