文章目錄

• 前言
• 整除分塊
• • 代碼
• 積性函數(shù)
• 線性篩
• 狄利克雷卷積
• 莫比烏斯反演
• trick

所謂莫比烏斯反演，就是莫比烏斯進行的反演

（逃）

前言

在一些需要整除的式子和 $\gcd ,\mathrm{lcm}$ 等問題中發(fā)揮作用。

整除分塊

整除分塊是莫反的必要前置。

結論：

對于 $i\le n$，滿足 $?\frac{n}{x}?=?\frac{n}{i}?$ 的最大的 $x$ 為 $?\frac{n}{?\frac{n}{i}?}?$。

證明：
設 $k=?\frac{n}{i}?$，那么就有 $n=i?k+p(0\le p<i,p=n\mathrm{m}\mathrm{o}\mathrm{d}i)$，設 $x=i+d$，同理有 $n=(i+d)?k+p^{\prime }(0\le p^{\prime }<x,p^{\prime }=n\mathrm{m}\mathrm{o}\mathrm{d}x)$，化簡得 $p^{\prime }=p?dk$，由于 $p^{\prime }>0$，有 $d<?\frac{p}{k}?$。
那么就有：
$$x_{max}=i+d_{max}$$
$$=i+?\frac{p}{k}?$$
$$=i+?\frac{n\mathrm{m}\mathrm{o}\mathrm{d}i}{k}?$$
$$=?i+\frac{n??\frac{n}{i}??i}{?\frac{n}{i}?}?$$
$$=?\frac{n}{?\frac{n}{i}?}?$$
證畢。

代碼

(計算因數(shù)個數(shù)的前綴和）

ll calc(ll x){if(x<=0) return 0ll ans=0;for(ll l=1,r;l<=x;l=r+1){r=x/(x/l);(ans+=1ll*(r-l+1)*(x/l))%=mod;}return ans; }

積性函數(shù)

定義：

如果 $f:{\mathbb{Z}}^{+}\to \mathbb{C}$，則稱 $f(n)$ 為一個數(shù)論函數(shù)。
如果 $f(n)$ 為一個數(shù)論函數(shù)，且對于 $p\perp q$，$f(pq)=f(p)f(q)$，則稱 $f(n)$ 為一個積性函數(shù)。
如果 $f(n)$ 為一個積性函數(shù)，且對于任意 $p,q$，$f(pq)=f(p)f(q)$，則稱 $f(n)$ 為一個完全積性函數(shù)。

一個重要的性質：

對于 $p\perp q,d_1|p,d_2|1$，則有 $(d_1{d}_2)|(pq)$

證明：結合基本算數(shù)定理，$d_1,d_2$ 必然沒有共同因子，相乘后各個因子的次數(shù)還是不超過原來的 $p,q$ 對應位置的次數(shù)。

常見的積性函數(shù)：

除數(shù)函數(shù)：${\sigma }_k(n)={\sum }_{d|n}{d}^k$。

證明：
$p\perp q\to {\sigma }_k(p){\sigma }_k(q)=({\sum }_{d_1|p}{d}_1^k)({\sum }_{d_2|q}{d}_2^k)={\sum }_{(d_1{d}_2)|(pq)}(d_1{d}_2{)}^k={\sigma }_k(pq)$。

約數(shù)個數(shù)函數(shù)：$\tau (n)={\sigma }_0(n)={\sum }_{d|n}1$。

約數(shù)和函數(shù)：$\sigma (n)={\sum }_{d|n}d$。

歐拉函數(shù)：$\phi (n)={\sum }_{i=1}^n[\gcd (i,n)=1]$。

證明：
$p\perp q\to {\phi }_{(}p){\phi }_k(q)=(p{\prod }_{a\in prime,a|p}\frac{a?1}{a})(q{\prod }_{b\in prime,b|q}\frac{b?1}{b})=pq{\prod }_{c\in prime,c|pq}\frac{c?1}{c}=\phi (pq)$

性質：$\phi (n)={\sum }_{i=1}^n[\gcd (i,n)=1]?i=\frac{\phi (n)+[n==1]}{2}$。
證明：對于 $\gcd (d,n)=1$，同樣有 $\gcd (n?d,n)=1$，所有和 $n$ 互質的數(shù)都是對稱分布的。

莫比烏斯函數(shù)：$\mu (n)$，$\mu (1)=1$，對于無平方因子的數(shù) $n={\prod }_i^k{p}_i$，$\mu (n)=(?1{)}^k$；對于有平方因子的數(shù) $n$，$\mu (n)=0$。

元函數(shù)：$e(n)=[n=1]$。完全積性。

恒等函數(shù)：$I(n)=1$。完全積性。也可寫作 $1(n)=1$。

單位函數(shù)：$id(n)=n$。完全積性。

恒等函數(shù)：$i{d}^k(n)=n^k$。完全積性。

線性篩

利用線性篩篩出 $\mu$ 這樣的積性函數(shù)。

int mu[N]; int p[N],tot,vis[N]; void init(int n){mu[1]=1;for(int i=2;i<=n;i++){if(!vis[i]) vis[i]=1,mu[i]=-1,p[++tot]=i;for(int j=1;j<=tot&&p[j]<=n/i;j++){vis[i*p[j]]=1;if(i%p[j]==0){mu[i*p[j]]=0;break;}mu[i*p[j]]=-mu[i];}} }

狄利克雷卷積

定義：

對于數(shù)論函數(shù) $f,g$，$h(n)=f?g={\sum }_{d|n}f(d)g(\frac{n}{d})$ 叫做 $f,g$ 的狄利克雷卷積。
狄利克雷卷積可以理解為乘法意義上的卷積，滿足交換律、分配律，結合律。

若 $f,g$ 均為積性函數(shù)，那么 $h=f?g$ 也是積性函數(shù)。

證明：$p\perp q\to h(p)h(q)=({\sum }_{d_1|p}f(d_1)g(\frac{p}{d_1}))({\sum }_{d_2|q}f(d_2)g(\frac{q}{d_2}))={\sum }_{(d_1{d}_2)|(pq)}f(d_1)f(d_2)g(\frac{p}{d_1})g(\frac{q}{d_2})={\sum }_{(d_1{d}_2)|(pq)}f(d_1{d}_2)g(\frac{pq}{d_1{d}_2})=h(pq)$

$1?1=\tau$
$1?id=\sigma$

證明：直接展開即可得。

${\sum }_{d|n}\mu (d)=[n==1]$，即 $\mu ?1=e$，兩者互為逆元。

證明：$\mu (1)=0$ 顯然成立，對于 $n>1$，由于含平方因子的 $\mu$ 均為0，只需要考慮 $n$ 所有不含平方因子的因數(shù)。
設 $n$ 有 $m$ 個質因子，從這些質因子中任意選擇（每項最多一個）構成因數(shù)，就有：${\sum }_{d|n}\mu (d)={\sum }_{i=0}^m\left(\genfrac{}{}{0ex}{}{m}{i}\right)(?1{)}^i=(1?1{)}^m=0$。

$[\gcd (i,j)=1]={\sum }_{d|\gcd (i,j)}\mu (d)$

證明：直接令上一個式子 ${\sum }_{d|n}\mu (d)=[n==1]$ 的 $n=\gcd (i,j)$ 即可得。

$\phi =\mu ?id$

證明：$(\mu ?id)(n)={\sum }_{d|n}\mu (d)\frac{n}{d}$，右邊的式子就可以理解成容斥篩掉所有和 $n$ 不互質的數(shù)。

$id=\phi ?1,n=id(n)={\sum }_{d|n}\phi (n)$

證明：$id=id?e=id?\mu ?1=\phi ?1$

莫比烏斯反演

若 $g(n)={\sum }_{d|n}f(d)$，那么 $f(n)={\sum }_{d|n}\mu (d)g(\frac{n}{d})$。

證明：

$f=f?1?\mu =g?\mu$。

${\sum }_{d|n}\mu (d)g(\frac{n}{d})={\sum }_{d|n}\mu (d){\sum }_{k|\frac{n}{d}}f(k)={\sum }_{kd|n}\mu (d)f(k)={\sum }_{k|n}f(k){\sum }_{d|\frac{n}{k}}\mu (d)$
$={\sum }_{k|n}f(k)[\frac{n}{k}=1]=f(n)$

若 $g(n)={\sum }_{n|d}f(d)$，那么 $f(n)={\sum }_{n|d}\mu (\frac{d}{n})g(d)$。

證明：${\sum }_{n|d}\mu (\frac{d}{n})g(d)={\sum }_{k=1}^{\infty }\mu (k)g(kn)={\sum }_{k=1}^{\infty }\mu (k){\sum }_{d|kn}f(d)={\sum }_{n|d}f(d){\sum }_{k|\frac{d}{n}}\mu (k)$
$={\sum }_{n|d}f(d)[\frac{d}{n}=1]=f(n)$

trick

枚舉倍數(shù)的一種靈活的變形：$g(d)={\sum }_{d|i}^{n}f(i)={\sum }_{i=1}^{?\frac{n}{d}?}f(i?d)$。
很顯然，但有時能發(fā)揮大作用。

$[\gcd (i,j)=1]={\sum }_{d|\gcd (i,j)}\mu (d)$。再寫一遍是因為它太重要了。

關于因數(shù)個數(shù)函數(shù)：$\tau (i?j)={\sum }_{x|i,y|j}[\gcd (x,y)=1]$。

總結

以上是生活随笔為你收集整理的模板：莫比乌斯反演（数论）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。