莫比烏斯反演初探 -开发者知识库

莫比烏斯反演初探 -开发者知识库,第1张

本文的部分latex垮掉了。我也不知道為什么(有毒),建議將代碼拷貝至本地md編編輯器閱讀。

數論(整除)分塊

整除分塊:設函數\(f(x)=\lfloor\frac{N}{x}\rfloor, x\in N^ \),期望在根號時間內求得\(\sum_{x} f(x)\)的值。

【定理1】\(f(x)\)的值域大小不超過\(2\sqrt{N}\)

【定理2】若\(x=q\)\(f(x)=p\)的解,則\(x=\lfloor\frac{N}{\lfloor N/q\rfloor}\rfloor\)\(f(x)=p\)的最大解。

證明如下

\[ \text{make } N=pq r(0\le r<q) \ \text{make } N=p*(q k) t(0\le t<q d) \ pk t=r\ t=r-pk\ge 0 \ k\le\lfloor \frac{r}{p}\rfloor=\lfloor \frac{N\bmod q}{p}\rfloor \ \begin{aligned} x_{\max}&=q k_{\max} \ &=q \lfloor \frac{N\bmod q}{p}\rfloor\ &=q \lfloor \frac{N-\lfloor N/q\rfloor*q}{\lfloor N/q\rfloor}\rfloor\ &=\lfloor q \frac{N-\lfloor N/q\rfloor*q}{\lfloor N/q\rfloor}\rfloor\ &=\lfloor\frac{\lfloor N/q\rfloor*q N-\lfloor N/q\rfloor*q}{\lfloor N/q\rfloor}\rfloor\ &=\lfloor\frac{N}{\lfloor N/q\rfloor}\rfloor\ \end{aligned} \]

莫比烏斯函數

【定義】

定義 \(\mu(d)\)
\[ \mu(d)=\begin{cases} 1&d=1\ (-1)^k&d=\Pi^{k}_{i=1}P_i\ 0&else \end{cases} \]
\(\mu(d)\) 為關於 \(d\) 的莫比烏斯函數。

【性質】

  • 對於任意 \(n\in N^*\) ,有 \(\sum_{d|n}\mu(d)=[n=1]\)
  • 對於任意 \(n\in N^*\) ,有 \(\sum_{d|n}\dfrac{\mu(d)}{d}=\dfrac{\phi(n)}{n}\)

【 遞推】 結合線性篩素數。

【配套練習 】

YY的GCD

\[ \begin{aligned} r&=\sum_{p\in\Pr}\sum _{x=1}^n\sum_{y=1}^m [\gcd(x,y)=p]\ &=\sum_{p=\Pr}\sum_{x=1}^{\lfloor n/p\rfloor}\sum_{y=1}^{\lfloor m/p\rfloor}[\gcd(x,y)=1] &\star\ r&=\sum_{p=\Pr}\sum_{x=1}^{\lfloor n/p\rfloor}\sum_{y=1}^{\lfloor m/p\rfloor}\sum_{d|\gcd(x,y)}\mu(d) &\star\ &=\sum_{p=\Pr}\sum_{d=1}^{\lfloor\frac{\min(n,m)}{p}\rfloor}\mu(d)\sum_{x=1}^{\lfloor n/p\rfloor}\sum_{y=1}^{\lfloor m/p\rfloor}[d|\gcd(x,y)]\ &=\sum_{p=\Pr}\sum_{d=1}^{\lfloor\frac{\min(n,m)}{p}\rfloor}\mu(d)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor\ \text{設 }k&=pd\ r&=\sum_{p=\Pr}\sum_{d=1}^{\lfloor\frac{\min(n,m)}{p}\rfloor}\mu(\frac{k}{p})\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor\ &=\sum_{k=1}^{\min(n,m)}\sum_{p\in\Pr,p\mid k}\mu(\frac{k}{p})\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor\ \text{預處理}f(k)&=\sum_{p\in\Pr,p\mid k}\mu(\frac{k}{p})\text{對於所有的 k(s)}\ r&=\sum_{k=1}^{\min(n,m)}f(k)\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor\ \end{aligned} \]

[國家集訓隊]Crash的數字表格

\[ \begin{aligned} r(n,m)&=\sum_{i=1}^n\sum_{j=1}^m\frac{i*j}{\gcd(i,j)}\ &=\sum_{d}\sum_{i=1}^n\sum_{j=1}^m\frac{i*j}{d} [\gcd(i,j)=d]\ &=\sum_{d}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}d*i*j[\gcd(i,j)=1]\ &=\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i*j[\gcd(i,j)=1]\ q(n,m)&=\sum_{i=1}^n\sum_{j=1}^m i*j[\gcd(i,j)=1] &\star\ &=\sum_{i=1}^n\sum_{j=1}^m i*j\sum_{k|gcd(i,j)}\mu(k) &\star\ &=\sum_{k=1}^{\min(n,m)}\mu(k)\sum_{k\mid i}^n\sum_{k\mid j}^m i*j\ &=\sum_{k=1}^{\min(n,m)}\mu(k)\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor} i*j*k^2\ &=\sum_{k=1}^{\min(n,m)}k^2\mu(k)\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor} i*j\ r(n,m)&=\sum_{d=1}^{\min(n,m)}d*q(d,\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor) \end{aligned} \]

莫比烏斯反演

【定理1】若 \(F(n)\)\(f(n)\) 是定義在 \(N\) 上的兩個函數,且滿足 \(F(n)=\sum_{d\mid n}f(d)\),那么 \(f(n)=\sum_{d\mid n}\mu(d)F(\dfrac{n}{d})\)
證明:
\[ \begin{aligned} \sum_{d\mid n}\mu(d)F(\dfrac{n}{d})&=\sum_{d\mid n}\mu(d)\sum_{i\mid\dfrac{n}{d}}f(i)\ &=\sum_{i\mid n}f(i)\sum_{d\mid\dfrac{n}{i}}\mu(d)\ &=f(n) &\star\ \end{aligned} \]

【定理2】若 \(F(n)\)\(f(n)\) 是定義在 \(N\) 上的兩個函數,且滿足 \(F(n)=\sum_{n\mid d}f(d)\),那么 \(f(n)=\sum_{n\mid d}\mu(\dfrac{d}{n})F(d)\)

【配套練習】

[SDOI2015] 約數個數和

[SDOI2014] 數表

\[ \text{在忽略a的限制下} \begin{aligned} F(x)&=\sum_{d\mid x} d \ r(n,m)&=\sum_{i=1}^n\sum_{j=1}^m F(\gcd(i,j))\ &=\sum_{d=1}^{\min(n,m)}F(d)\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]\ &=\sum_{d=1}^{\min(n,m)}F(d)\sum_{d|k}\mu(\frac{k}{d})\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor\ &=\sum_{k=1}^{\min(n,m)}\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor\sum_{d\mid k}F(d)\mu(\frac{k}{d}) \end{aligned} \]

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复