數(shù)論下

前言

疊甲：本文的許多定義并不是最官方嚴(yán)謹(jǐn)?shù)模瞧鋵?shí)是本質(zhì)相同的，不過(guò)更偏實(shí)用一點(diǎn)。有部分內(nèi)容我并沒(méi)有寫(xiě)代碼驗(yàn)證過(guò)，可能有錯(cuò)，希望發(fā)現(xiàn)問(wèn)題的大佬能及時(shí)指出。歡迎轉(zhuǎn)載。但如果是全文轉(zhuǎn)載，請(qǐng)附上原文鏈接。因?yàn)椴┛蛨@與本地的渲染有細(xì)微差別，可能會(huì)導(dǎo)致有少量格式錯(cuò)誤，但應(yīng)該不會(huì)影響閱讀，也歡迎大佬指出。

這不是給數(shù)論初學(xué)者寫(xiě)的博客！這是作者在整理各種數(shù)論知識(shí)的邊邊角角梳理出來(lái)的文章，不保證內(nèi)容按照難度遞增，而是按照邏輯順序排列的，相關(guān)聯(lián)的知識(shí)點(diǎn)會(huì)放在一起。文章分為前、中、后和配套題目與題解四個(gè)部分，分成四偏文章的原因是，放在一起會(huì)導(dǎo)致非常卡，猜測(cè)是因?yàn)槲恼绿罅耍總€(gè)部分之間有著藕斷絲連的關(guān)系，前三部分是知識(shí)點(diǎn)，有著互相依賴(lài)的邏輯關(guān)系（但是保證不會(huì)有自己證明自己的情況出現(xiàn)），第四篇是具體的題目，對(duì)提分來(lái)說(shuō)更加重要。建議配合食用。

本文很多內(nèi)容是我之前寫(xiě)的博客復(fù)制過(guò)來(lái)，修繕了一下，個(gè)人感覺(jué)比之前寫(xiě)的更本質(zhì)，更清晰一點(diǎn)，還有不少內(nèi)容是我這次整理新學(xué)的知識(shí)。四篇文章總源碼超過(guò) 100 KB，我認(rèn)為整理的還是比較全面了，沒(méi)有涉及到的內(nèi)容，大概率在數(shù)論練習(xí)題里的后記里面提及。

合集鏈接：數(shù)論上，數(shù)論中，數(shù)論下，數(shù)論練習(xí)題。

因數(shù)與數(shù)論函數(shù)

基礎(chǔ)

基礎(chǔ)概念與定義

• 素?cái)?shù)
• 因數(shù)
• 倍數(shù)
• 約數(shù)
• 最小公因數(shù)/最大公倍數(shù)

不用做過(guò)多解釋。

整數(shù)唯一分解定理/算術(shù)基本定理

內(nèi)容：任何一個(gè)大于 \(1\) 的正整數(shù)都可以被唯一分解成有限個(gè)質(zhì)數(shù)的次冪的乘積。

證明：感性理解即可。不會(huì)真的有人會(huì)想要去嚴(yán)謹(jǐn)證明這個(gè)東西吧？

素?cái)?shù)判定/分解質(zhì)因數(shù)/得到約數(shù)

• 試除法

本質(zhì)上是根號(hào)分治。只枚舉 \([1,\sqrt n]\)，判斷它是不是 \(n\) 的約束，一般用這個(gè)足夠了。不過(guò)多解釋。

• 倍數(shù)法

用于要處理 \([1,N]\) 之間所有數(shù)的約數(shù)之類(lèi)的問(wèn)題。

可以理解為篩法。對(duì)于每一個(gè)數(shù)，標(biāo)記它的所有倍數(shù)含有它這個(gè)因子。復(fù)雜度就是標(biāo)準(zhǔn)的調(diào)和級(jí)數(shù) \(O(N\log N)\)。當(dāng)然也可以只標(biāo)注每個(gè)數(shù)的最小質(zhì)因子，通過(guò)每次除掉它的最小質(zhì)因子，可以分解出它的所有質(zhì)因數(shù)，這個(gè)隨便用個(gè)什么篩法都能篩出來(lái)。

這也恰好說(shuō)明了約數(shù)個(gè)數(shù)平均下來(lái)是 \(O(\log N)\) 的。

找到一個(gè)倍數(shù)法的水題：P7960 NOIP2021報(bào)數(shù) - 洛谷，這個(gè)題就是倍數(shù)法標(biāo)記不合法的數(shù)，加點(diǎn)剪枝。

• Miller_Rabin ~ Pollard Rho（理性愉悅，不用講）

前者 \(O(\log n)\)，有一個(gè)比較大的常數(shù)；后者 \(O(n^{1\over4})\) ，但是是期望復(fù)雜度，實(shí)則跑的飛快。

如果要求約數(shù)，可以在分解了質(zhì)因數(shù)后 dfs 其指數(shù)。

把之前寫(xiě)的博客粘過(guò)來(lái)后覺(jué)得格式太丑了，于是沒(méi)粘過(guò)來(lái)，所以要學(xué)的同學(xué)直接去看我之前寫(xiě)的博客即可，我認(rèn)為寫(xiě)得非常詳細(xì)。詳見(jiàn)這里.

數(shù)論分塊（整除分塊）

對(duì)于類(lèi)似于 \(solve_{d=1}^{n}(\frac{n}w0obha2h00)\) 的式子, \(\frac{n}w0obha2h00\) 的值的個(gè)數(shù)不超過(guò) \(\sqrt n\) 個(gè)（下面有證明），故可以對(duì)于每一個(gè)結(jié)果去計(jì)算其貢獻(xiàn)。

代碼如下:

for(int l = 1, r; l <= n; l = r + 1) {
   r = n / (n / l);// d 在區(qū)間 [l, r] 的 n/d 大小相同
   ans += n / l * solve(l, r);
}

復(fù)雜度證明：

記 \(\dfrac{n}w0obha2h00\) 為 \(x\)。\(x\) 的取值范圍在 \([1,n]\)。容易發(fā)現(xiàn)，\([1,\sqrt n]\) 的 \(x\) 更密集，\((\sqrt n, n]\) 的 \(x\) 更稀疏。

因?yàn)?\(d\) 從 \(1\) 到 \(n\) ，只有 \(d\) 在 \([1, \sqrt n]\) 時(shí)，\(\dfrac{n}w0obha2h00\) 在 \((\sqrt n, n]\)，所以\(\dfrac{n}w0obha2h00\) 在 \((\sqrt n, n]\) 的個(gè)數(shù)不超過(guò) \(\sqrt n\).

\(\dfrac{n}w0obha2h00\) 從 \(1\) 到 \(\sqrt n\) 一共 \(\sqrt n\) 個(gè)數(shù)，所以總個(gè)數(shù)為 \(O(\sqrt n)\) 的，本質(zhì)上就是一個(gè)根號(hào)分治的思想。

一般式子中出現(xiàn)下取整，并且是分母一直在變，直接無(wú)腦整除分塊。（P.S. 如果是分子在變，可以考慮類(lèi)歐或萬(wàn)歐，分子分母都在變，可以考慮是否可讓一個(gè)不變）

\(solve_{d=1}^{n}(\frac{a}w0obha2h00\frac bd)\) 這種式子也可以整除分塊。

for(int l = 1, r; l <= n; l = r + 1) {
	r = min({n, a / (a / l), b / (b / l)});
	ans = ans + 1ll * (b / l) * (a / l) * (sm[r] - sm[l - 1]);
}

復(fù)雜度 \(O(\sqrt n)\)。

這相當(dāng)于在數(shù)軸上對(duì) \(a\) 撒 \(O(\sqrt n)\) 個(gè)點(diǎn)，對(duì) \(b\) 撒 \(O(\sqrt n)\) 個(gè)點(diǎn)，加起來(lái)還是 \(O(\sqrt n)\) 個(gè)點(diǎn)。

數(shù)論函數(shù)相關(guān)

積性函數(shù)

• 基礎(chǔ)定義

積性定義： \(f(ab)=f(a)f(b)\) ( \(a,b\) 互質(zhì)時(shí))

具有積性的函數(shù)叫積性函數(shù)。

如果 \(a,b\) 不互質(zhì)時(shí)上式仍然成立，那就是完全積性函數(shù)。

邊界：積性函數(shù)在 \(1\) 處的取值為 \(1\)。這樣定義更為方便，不然每次都要分討 1 的情況很麻煩。

• 積性函數(shù)性質(zhì)（摘自 oi-wiki，并給出了 oi-wiki 不屑于寫(xiě)的證明）

對(duì)正整數(shù) \(x\) ，設(shè)其唯一質(zhì)因數(shù)分解為 \(x=\prod p_{i}^{k_{i}}\) ，其中 \(p_{i}\) 為質(zhì)數(shù)。
若 \(F(x)\) 為積性函數(shù)，則有 $F(x)=\prod F\left(p_{i}^{k_{i}}\right) $ 。
若 \(F(x)\) 為完全積性函數(shù)，則有 $F(x)=\prod F\left(p_{i}^{k_{i}}\right)=\prod F\left(p_{i}\right)^{k_{i}} $ 。

若 \(f(x)\) 和 \(g(x)\) 均為積性函數(shù)，則以下函數(shù)也為積性函數(shù)：

1. \(h(x)=f\left(x^{p}\right)\)

證明：
設(shè) \(a\) 和 \(b\) 是互質(zhì)的整數(shù)，我們需要證明 \(h(ab) = h(a)h(b)\)。

由于 \(f\) 是積性函數(shù)，我們有：

因此，\(h(x) = f(x^p)\) 是積性函數(shù)。

2. \(h(x) =f(x) g(x)\)

證明： \(h(ab) = f(ab)g(ab) = (f(a)f(b))(g(a)g(b)) = (f(a)g(a))(f(b)g(b)) = h(a)h(b)\).

推論：\(h(x) =f^{p}(x)\).

3. \(h(x) =\sum_{d \mid x} f(d) g\left(\frac{x}w0obha2h00\right)\)

證明：
由于 \(a\) 和 \(b\) 互質(zhì)，\(d\) 可以唯一地表示為 \(d = d_1d_2\)，其中 \(d_1|a\) 且 \(d_2|b\)。因此，

由于 \(f\) 和 \(g\) 是積性函數(shù)，我們可以將上式重寫(xiě)為：

因此，\(h(x) = \sum_{d|x} f(d)g\left(\frac{x}w0obha2h00\right)\) 是積性函數(shù)。

最后這個(gè)性質(zhì)是莫反的基礎(chǔ)。

• 常見(jiàn)的積性函數(shù)

1. 單位函數(shù)：\(\varepsilon(n)=[n=1]\)（完全積性）
2. 恒等函數(shù)：\(\operatorname{id}_k(n)=n^k\)（完全積性），當(dāng) \(k=1\) 時(shí)，簡(jiǎn)記為 \(id(n)=n\)
3. 常數(shù)函數(shù)：\(\operatorname{1}(n)=1\)（完全積性）
4. 除數(shù)函數(shù)：\(\sigma_k(n)=\sum_{d|n}d^k\)，特殊地，\(\sigma_0(n)\) 即因數(shù)個(gè)數(shù)，簡(jiǎn)記為 \(\operatornamew0obha2h00(n)\)；\(\sigma_1(n)\) 即因數(shù)之和，簡(jiǎn)記為 \(\sigma(n)\)
5. 歐拉函數(shù)：\(\varphi(n)=\sum_{d=1}^n[\gcd(d,n)=1]\)
6. 莫比烏斯函數(shù)：\(\mu(x)=\begin{cases}1\ \ &(x=1)\\(-1)^k\ \ &(\text{x沒(méi)有平方數(shù)因子，且x的質(zhì)因子個(gè)數(shù)為k})\\0 &(\text{x有平方數(shù)因子})\end{cases}\)

這些積性函數(shù)都可以用線性歐拉篩 \(O(n)\) 地篩出。

除了積性函數(shù)，當(dāng)然也可以定義加性函數(shù)，比如“質(zhì)因子數(shù)目”就是一個(gè)加性函數(shù)，不過(guò)我目前沒(méi)有發(fā)現(xiàn)加性函數(shù)有什么用。

篩法

• 概述

一般的篩法可以篩出某個(gè)范圍內(nèi)的素?cái)?shù)。

用恰當(dāng)?shù)暮Y法可以篩出具有某種性質(zhì)的數(shù)論函數(shù)，或某種數(shù)論函數(shù)的前綴和。

首先有一個(gè)樸素算法是枚舉每個(gè)數(shù)，然后遍歷它們的倍數(shù)，然后再計(jì)算這些數(shù)對(duì)它們的倍數(shù)的貢獻(xiàn)。復(fù)雜度是 \(O(n\ln n)\).

埃氏篩

本質(zhì)上是對(duì)樸素算法的優(yōu)化，結(jié)果一不小心把復(fù)雜度優(yōu)化了。

• 復(fù)雜度

\(O(n\log\log n)\) 并且常數(shù)很小，所以可以近似看作 \(O(n)\)。復(fù)雜度不會(huì)證明。OI-wiki 上給出了一些神秘常數(shù)優(yōu)化方法，不過(guò)我沒(méi)看懂。

• 適用范圍

只需要篩素?cái)?shù)的題。其實(shí)也可以篩一些簡(jiǎn)單的積性函數(shù)，不過(guò)不如歐拉篩。下文只講篩素?cái)?shù)的方法。

優(yōu)化 1 ：只用處理素?cái)?shù)的倍數(shù)。這樣每個(gè)合數(shù)都會(huì)被它某些素因子篩掉。

優(yōu)化 2 ：對(duì)于每一個(gè)素?cái)?shù) \(p\)，只標(biāo)記 \(p^2 + kp,k\ge0\) 為合數(shù)，也就是說(shuō)直接從平方這里開(kāi)始往后篩合數(shù)。

優(yōu)化 2 的正確性：假設(shè) \((p,p^2)\) 內(nèi)存在一個(gè)含有 \(p\) 這個(gè)因子的合數(shù)沒(méi)被篩掉，那這個(gè)合數(shù)一定可以被寫(xiě)為 \(pxq,x\in z,q\) 是這個(gè)合數(shù)的質(zhì)因子，并且不同于 \(p\)。

因?yàn)?\(pxq\) 小于 \(p^2\)，所以 \(q \le p\)，所以這個(gè)數(shù)會(huì)被 \(q\) 篩掉，假設(shè)不成立。

所以可以每次遇到一個(gè)不是合數(shù)的數(shù)，就認(rèn)為它是素?cái)?shù)。

附上代碼：

void ash_shai(int n) {
	ll i = 2; for(; i * i <= n; ++i) if(!vis[i]) {
		pri.push_back(i);
		for(ll j = i * i; j <= n; j += i) vis[j] = true;
	} for(; i <= n; ++i) if(!vis[i]) pri.push_back(i);
}

歐拉篩

又稱(chēng)線性篩。

• 原理：讓每個(gè)數(shù)只被它的最小質(zhì)因子篩掉

• 復(fù)雜度： \(O(n)\)

• 主要用處：篩積性函數(shù)值

我們對(duì)于每一個(gè)數(shù) \(i\)，枚舉小于等于它的最小質(zhì)因子并與其互質(zhì)的質(zhì)數(shù) \(p\)，把由它倆乘積肯定是合數(shù)，把這個(gè)合數(shù)篩掉。

正確性：考慮反證法。假設(shè)有一個(gè)數(shù)不是被它的最小質(zhì)因子篩掉的，假設(shè)是 \(q\)，因?yàn)?\(q\) 是質(zhì)數(shù)，所以此時(shí)這個(gè)合數(shù)的最小質(zhì)因子一定在 \(i\) 中，這不符合算法流程。假設(shè)有一個(gè)數(shù)沒(méi)有被篩掉，假設(shè)它是 \(x\)，它的最小質(zhì)因子是 \(p\)，那么在枚舉 \(x/p\) 的時(shí)候一定會(huì)枚舉到 \(p\)，假設(shè)不成立。證畢。

每次遇到一個(gè)不是合數(shù)的數(shù)，就認(rèn)為它是素?cái)?shù)。

不過(guò)更重要的是用歐拉篩去篩函數(shù)值。

可以被歐拉篩篩出來(lái)的函數(shù)必須滿(mǎn)足以下性質(zhì)：

對(duì)于 \(k = 1, k \in prime, k \mid p\)， \(f(pk)\) 可以由 \(f(p)\) 和 \(f(k)\) 快速得到，并且知道 \(f(1)\) 的值。

所以大部分的積性函數(shù)都可以用歐拉篩線性地篩出函數(shù)值。

例如 \(\varphi\) 和 \(\mu\)：

\(\varphi(1) = \mu(1) = 1\)

\(\varphi(p) = p - 1, \mu(p) = 1\)

\(\varphi(pk) = \varphi(p)*\varphi(k) = (k-1)\varphi(p),\mu(pk) = \mu(p)*\mu(k) = -\mu(p)\)，\(k\) 是質(zhì)數(shù)，且 \(k,p\) 互質(zhì)。

\(\varphi(pk) = k\varphi(p),\mu(pk) = 0,k \in prime, k\mid p\)

代碼：

void get_oula(int M){
	phi[1] = 1, mu[1] = 1;
	for(int i = 2; i <= M; ++i) {
		if(!vis[i]) pri.push_back(i), phi[i] = i - 1, mu[i] = -1; // k=1
		for(int j : pri) {//k is prime
			if(i*j>M) break;
			vis[i*j] = 1;
			phi[i*j] = phi[i] * (j - 1);
			mu[i*j] = mu[i] * (-1);
			if(i % j == 0){//k | p
				phi[i*j] = phi[i] * j;
				mu[i*j] = 0;
				break;
			}
		}
	}
}

杜教篩

• 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：1. 復(fù)雜度 \(O(n^{2\over 3})\).2. 可以得到前綴和。

缺點(diǎn)：只能得到函數(shù)的部分函數(shù)值的前綴和。對(duì)要篩的函數(shù)有很多限制。

• 算法實(shí)現(xiàn)

對(duì)于數(shù)論函數(shù) \(f\)，計(jì)算 \(S(n)=\sum_{i=1}^{n}f(i)\)。

需要找到一個(gè)合適的函數(shù) \(g\)，來(lái)和 \(f\) 進(jìn)行卷積。

如果 \(g(1),\sum_i^n(f\otimes g)(i),\sum^{n}_{d=2}g(d)\) 這三個(gè)都是能快速求到的，那么就可以用整除分塊來(lái)遞歸地做。

最后一個(gè)問(wèn)題：這個(gè)是什么時(shí)間復(fù)雜度？

觀察到：當(dāng)\(a,b\gt0\) 且 \(b\in \Z\) 時(shí)， \(\left\lfloor\frac{\lfloor\frac na\rfloor}{b}\right\rfloor=\left\lfloor\frac{n}{ab}\right\rfloor\)，所以無(wú)論怎么遞歸，S 會(huì)計(jì)算到的數(shù)只在集合 \(\{\left\lfloor\frac nx\right\rfloor\}\) 中，只有 \(O(\sqrt n)\) 個(gè)。用微積分的知識(shí)，可以得到時(shí)間復(fù)雜度是 \(O(n^{3\over4})\)

不過(guò)我們還可以通過(guò)暴力預(yù)處理（歐拉篩）前面的 \(2\over3\)，使時(shí)間復(fù)雜度降到 \(O(n^{2\over3})\).

最大的問(wèn)題在與要有合適的 \(g\)。我們發(fā)現(xiàn) 常數(shù)函數(shù) \(1\) 對(duì) \(\varphi\) 和 \(\mu\) 就滿(mǎn)足此性質(zhì)。

把 \(\mu\) 帶到我們的式子里：

即：

\(\operatorname{1}(i)\) 的前綴和就是 \(i\)。杜教篩時(shí)間復(fù)雜度 \(O(n^{\frac{2}{3}})\)

對(duì)于 \(\varphi\) 帶到我們的式子里：

即：

\(\operatorname{1}(i)\) 的前綴和就是 \(i\)。杜教篩時(shí)間復(fù)雜度 \(O(n^{\frac{2}{3}})\)

我們還發(fā)現(xiàn) \(\mu·id_k\) 和 \(\varphi·id_k\) 可以找到 \(id_k\) 作為它們的函數(shù) \(g\)。（注：這里的點(diǎn)乘表示的是對(duì)應(yīng)位置相乘，即 ：\((f·g)(n) = f(n)g(n)\)）

Powerful Number篩

這玩意相比杜教篩，優(yōu)點(diǎn)是對(duì) \(g\) 的限制更少，可以處理更積性的 \(f\)，缺點(diǎn)是寫(xiě)起來(lái)更史。

• 前置：Powerful Number

定義：對(duì)于正整數(shù) \(n\)，記 \(n\) 的質(zhì)因數(shù)分解為 \(n = \prod_{i=1}^{m} p_{i}^{e_{i}}\)。\(n\) 是 Powerful Number（簡(jiǎn)稱(chēng) PN） 當(dāng)且僅當(dāng) \(\forall 1 \le i \le m, e_{i} > 1\)。

PN 有如下性質(zhì)：

• 所有 PN 都可以表示成 \(a^{2}b^{3}\) 的形式。
  證明：若 \(e_i\) 是偶數(shù)，則將
  \(p_{i}^{e_{i}}\) 合并進(jìn) \(a^{2}\) 里；若 \(e_i\) 為奇數(shù)，則先將 \(p_{i}^{3}\) 合并進(jìn) \(b^{3}\) 里，再將 \(p_{i}^{e_{i}-3}\) 合并進(jìn) \(a^{2}\) 里。

• \(n\) 以?xún)?nèi)的 PN 有 \(O(\sqrt{n})\) 個(gè)。

證明：考慮枚舉 \(a\)，再考慮滿(mǎn)足條件的 \(b\) 的個(gè)數(shù)，有 PN 的個(gè)數(shù)約等于

那么如何求出 \(n\) 以?xún)?nèi)所有的 PN 呢？線性篩找出 \(\sqrt{n}\) 內(nèi)的所有素?cái)?shù)，再 DFS 搜索各素?cái)?shù)的指數(shù)即可。由于 \(n\) 以?xún)?nèi)的 PN 至多有 \(O(\sqrt{n})\) 個(gè)，所以至多搜索 \(O(\sqrt{n})\) 次。

Powerful Number篩要求存在一個(gè)函數(shù) \(g\) 滿(mǎn)足：

• \(g\) 是積性函數(shù)。

• \(g\) 易求前綴和。

• 對(duì)于質(zhì)數(shù) \(p\)，\(g(p) = f(p)\)。

假設(shè)現(xiàn)在要求積性函數(shù) \(f\) 的前綴和.

首先，構(gòu)造出一個(gè)易求前綴和的積性函數(shù) \(g\)，且滿(mǎn)足對(duì)于素?cái)?shù) \(p\)，\(g(p) = f(p)\)。記 \(G(n) = \sum_{i=1}^{n} g(i)\)。

然后，設(shè)函數(shù) \(h\) 滿(mǎn)足 \(f = g \otimes h\)，根據(jù)狄利克雷卷積的性質(zhì)可以得知 \(h\) 也為積性函數(shù)，因此 \(h(1) = 1\)。

對(duì)于素?cái)?shù) \(p\)，\(f(p) = g(1)h(p) + g(p)h(1) = h(p) + g(p) \implies h(p) = 0\)。根據(jù) \(h(p)=0\) 和 \(h\) 是積性函數(shù)可以推出對(duì)于非 PN 的數(shù) \(n\) 有 \(h(n) = 0\)，即 \(h\) 僅在 PN 處取有效值。這是保證 PN 篩時(shí)間復(fù)雜度的基本原理。

現(xiàn)在，根據(jù) \(f = g \ast h\) 有：

\(O(\sqrt{n})\) 找出所有 PN，計(jì)算出所有 \(h\) 的有效值。對(duì)于 \(h\) 有效值的計(jì)算，只需要計(jì)算出所有 \(h(p^c)\) 處的值，就可以根據(jù) \(h\) 為積性函數(shù)推出 \(h\) 的所有有效值。

現(xiàn)在對(duì)于每一個(gè)有效值 \(d\)，計(jì)算
\(h(d)G\left(\left\lfloor \dfrac{n}w0obha2h00 \right\rfloor\right)\) 并累加即可得到 \(F(n)\)。

下面考慮計(jì)算 \(h(p^c)\)，一共有兩種方法：

• 直接推出 \(h(p^c)\) 僅與 \(p,c\) 有關(guān)的計(jì)算公式，再根據(jù)公式計(jì)算 \(h(p^c)\)
• 根據(jù) \(f = g \ast h\) 有 \(f(p^c) = \sum_{i=0}^c g(p^i)h(p^{c-i})\)，移項(xiàng)可得 \(h(p^c) = f(p^c) - \sum_{i=1}^{c}g(p^i)h(p^{c-i})\)，現(xiàn)在就可以枚舉素?cái)?shù) \(p\) 再枚舉指數(shù) \(c\) 求解出所有 \(h(p^c)\)。

復(fù)雜度 \(O(\sqrt n\log n)\)，而且這個(gè)上界比較寬松。

可惜的是，我們沒(méi)有 PN 篩的模板題。不過(guò) Min_25 篩的模板題可以用 PN 篩來(lái)做。

Min_25篩

咕咕咕

洲閣篩

咕咕咕

莫比烏斯反演

前置：Dirchlet 卷積

定義 \(\otimes\) ：

• Dirchlet 卷積的性質(zhì)

首先根據(jù)積性函數(shù)的第三條性質(zhì)，說(shuō)明積性函數(shù)的 Dirchlet 卷積還是積性函數(shù)。

更深入的學(xué)習(xí)：狄利克雷生成函數(shù)淺談 - 洛谷專(zhuān)欄，貝爾級(jí)數(shù) - 博客園。

其中，使用 DGF 來(lái)理解各種高級(jí)篩法有奇效。

標(biāo)準(zhǔn)莫反

剛才積性函數(shù)性質(zhì)那里得到這么一個(gè)東西，

如果把 \(g\) 函數(shù)當(dāng)成常數(shù)函數(shù) \(1\) ，則可得到：
若 \(f(x)\) 為積性函數(shù)，則 \(h(x)=\sum_{d\mid n} f(x)\) 也為積性函數(shù)。

如果現(xiàn)在已知的是 \(h(x)\) ，可否求出 \(f(x)\) 來(lái)？

這是一個(gè)反演的形式，也就是說(shuō)，我們只需要構(gòu)造一個(gè)合適的容斥系數(shù)即可解決上面的問(wèn)題，這個(gè)系數(shù)就是大名鼎鼎的莫比烏斯函數(shù)。

我們希望定義一個(gè)函數(shù) \(\mu\) 滿(mǎn)足下面這個(gè)式子：

需要打表/分討可以發(fā)現(xiàn)，當(dāng)定義 \(\mu(x)=\begin{cases}1\ \ &(x=1)\\(-1)^k\ \ &(\text{x沒(méi)有平方數(shù)因子，且x的質(zhì)因子個(gè)數(shù)為k})\\0 &(\text{x有平方數(shù)因子})\end{cases}\) ，就可以滿(mǎn)足這個(gè)式子。

先在有了莫反，考慮來(lái)證明這幾個(gè)式子：

1. \(\large{\mu\otimes 1 = \varepsilon }\)

因?yàn)?\(1(n) = \sum_{d\mid n}[d=1]\)，寫(xiě)成反演的形式就是這個(gè)公式。

當(dāng)然也可以定義 \(\mu\) 是滿(mǎn)足這個(gè)式子的函數(shù)，然后再推導(dǎo)莫反，這是 \(\mu\) 的另一種理解方式。做題用的最多最多的就是這個(gè)式子。

2. \(\large{\mu\otimes \operatorname{id} = \varphi }\)

推導(dǎo)：

3. \(\large{\varphi\otimes 1 = id}\)

對(duì)上一個(gè)式子套一個(gè)莫反即可。

4. \(1\otimes1 = \operatornamew0obha2h00\)

套定義即可，不必多說(shuō)。

5. \(id \otimes1 = \sigma\)

套定義即可，不必多說(shuō)。

6. \(id_k\otimes1 = \sigma_k\)

套定義即可，不必多說(shuō)。

前兩個(gè)換一種寫(xiě)法就是：\(\sum\limits_{d\mid n} \varphi (d) = n\), \(\sum\limits_{d\mid n} \mu (d) = [n=1]\)。這才是推式子經(jīng)常遇到的。

后面三個(gè)式子本質(zhì)相同，而且非常好理解。

個(gè)人感覺(jué) \(\varepsilon\) 相當(dāng)于積性函數(shù)中的單位元，\(\mu\) 相當(dāng)于 \(1\) 的逆元

莫反例題

莫反的題目一般是直接套用上面這些二級(jí)結(jié)論，一般不用標(biāo)準(zhǔn)莫反式子本身，所以要重點(diǎn)講一下莫反的題目。

不同莫反題的套路是很相似的。基本上看到有 \(\gcd,lcm，[k= 1]\) 之類(lèi)的玩意就可以無(wú)腦套上莫反。

• **例題1 **

求：

令 \(S(n) = \sum^n_i i = (n + 1) * n / 2,T=kd\)，那么上式等于：

后面是積性函數(shù)，用線性篩 \(O(n)\)，前面整除分塊。

積性證明：

設(shè) \(f(pq) = \sum_{xy|pq}\mu(xy)xy\) （\(p,q\) 互質(zhì)）

\(f(p)=\sum_{x|p}\mu(x)x,f(q)=\sum_{y|q}\mu(y)y\)

因?yàn)?\(p,q\) 互質(zhì)，所以 \(x,y\) 整除 \(p,q\) 中的其中一個(gè)。

欽定 \(x \mid p, y \mid q\)（注意，如果 \(xy\mid p\) 則，等價(jià)于把 \(xy\) 看成新的 \(x\)， 把 \(1\) 看作 \(y\)， 這種情況會(huì)在之前統(tǒng)計(jì)過(guò)）

\(f(pq) = \sum_{xy|pq}\mu(xy)xy = \sum_{x|p}\mu(x)x\sum_{y|p}\mu(y)y=f(p)f(q)\)

對(duì)于 \(f(j^2p) = f(jp) + \sum\mu(j^2x)j^2x = f(jp)\)，其中 \(j,p\) 互質(zhì)。

\(f(p) = \mu(1)1 + \mu(p)p\)，其中 \(p\) 是質(zhì)數(shù)。

\(f(1)=\mu(1)1 = 1\)。

• 例2：P5518 MtOI2019 幽靈樂(lè)團(tuán) / 莫比烏斯反演基礎(chǔ)練習(xí)題.

吐槽一下：這題是一道一點(diǎn)都不基礎(chǔ)莫比烏斯反演基礎(chǔ)練習(xí)題，要用到很多 \(\prod\) 的性質(zhì)，不過(guò)也可以無(wú)腦 exp ln 轉(zhuǎn)和式亂搞。

一些約定： \([i\perp j]\) 表示 \(\gcd(i,j)=1\)，\([p]\) 表示 該項(xiàng)只在 p 為真時(shí)存在，在 p 為假的時(shí)候不存在。上界默認(rèn)為 \(A,B,C\) 最大值。

下文大量運(yùn)用：累乘性質(zhì).

一看就很惡心。

先轉(zhuǎn)化題目：

括號(hào)里面等于 \({ij\over gcd(i,j)gcd(i,k)}\)，可以先算分子貢獻(xiàn)，再算分母貢獻(xiàn)。

因?yàn)橛校?/p>

所以我們可以只計(jì)算一下這兩個(gè)式子的值：

現(xiàn)在這個(gè)題被轉(zhuǎn)化成了六個(gè)子問(wèn)題了，

Type = 0

1：\(\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C}i\).

2：\(\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C}gcd(i,j)\).

令 \(T=d\times g\)，則：

中間括號(hào)里面用歐拉篩積性函數(shù)預(yù)處理，直接整除分塊 \(O(\sqrt n)\).

Type = 1

1: \(\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C}i^{i*j*k}\).

記 \(\sum_1^n 1= S(n) = {n(n + 1)\over 2}\)

2:\(\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C}gcd(i,j)^{ijk}\).

類(lèi)似于 type=0 - 2 ，中間可以歐拉篩預(yù)處理，然后整除分塊。

Type = 2

1 : \(\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C}i^{\gcd(i,j,k)}\).

整除分塊以后，那三個(gè)下取整都是定值，現(xiàn)在要求的是 \(\prod_T x^{\varphi(T)} = x^{\sum_T\varphi(T)}\) 和 \(\prod_T T^{\varphi(T)}\).

左邊的，可以通過(guò)求 \(\varphi\) 的前綴和，右邊的，把 \(\varphi\) 篩出來(lái)以后可以算 \(T^{\varphi(T)}\)，求一個(gè)前綴積即可。\(O(\sqrt n \log n + n)\).

2.\(\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C}\gcd(i,j)^{\gcd(i,j,k)}\).

先看左邊：

還是一個(gè)整除分塊 + 歐拉篩。

再來(lái)看右邊：

中間的還是可以歐拉篩，外層乍一看有兩個(gè) \(\prod\)，但實(shí)際上是整出分塊套整除分塊，所以加起來(lái)是 \(O(\sqrt[3\over4] n\log n)\).