（未更完）
我演算法中也就差點數論沒學了，這幾周卷了，學了一下，分享一下啊，
我會講得詳細一點，關于我不懂得地方，讓新手更容易理解，
學習反演有很多定義啥的必須要記的，學的時候容易崩潰，所以希望大家能堅持下來，
第一個定義：
$\lfloor x\rfloor$：意思是小于等于 $x$ 的最大整數，
數論分塊
學習反演之前，要先學習一些邊角料，先來看數論分塊（又名整除分塊），
最典型的一個例子是求 $\sum\limits_{i=1}^n \lfloor\frac{n}{i}\rfloor$，其中 $n\leq 10^{12}$，
首先，一個個回圈 $i$ 顯然會超時，所以考慮優化這個方法，
通過打表可以發現 $\lfloor\frac{n}{i}\rfloor$ 中有大部分值是相等的，且值的個數不超過 $2\sqrt{n}$，
函式影像長這樣：
下面來證明一下：
當 $i\leq \sqrt{n}$ 時：$i$ 的取值一共 $\sqrt{n}$，所以不同的值不會超過 $\sqrt{n}$，
當 $i\geq \sqrt{n}$ 時：$\lfloor\frac{n}{i}\rfloor\leq\sqrt{n}$，所以不同的值也不會超過 $\sqrt{n}$，
那么就可以列舉 $\lfloor\frac{n}{i}\rfloor$ 的值來 $\sqrt{n}$ 計算了，
具體怎么做呢，我們發現值相同的數成塊狀分布，假如知道塊的第一個是 $l$，那么塊的最后一個就是 $n / (n / l)$（這里默認下取整），
這個結論模擬一下就能懂，并且很好背，
代碼（現場寫的）：
for (int l = 1, r; l <= n; l = r + 1) { r = n / (n / l); ans += (n / l) * (r - l + 1); }
居然有個板子題，還是綠的：鏈接，別忘了開 $LL$ 啊，
數論分塊的變形
形式一：
求 $\sum\limits_{i=1}^n$ $k$ $mod$ $i$，
顯然：$k$ $mod$ $i=k-i\cdot\lfloor\frac{k}{i}\rfloor$，
化為：$\sum\limits_{i=1}^n$ $k-i\cdot\lfloor\frac{k}{i}\rfloor$，
$k$ 和回圈內的變數無關，把它提出來得到：$n\cdot k-\sum\limits_{i=1}^ni\cdot\lfloor\frac{k}{i}\rfloor$
$\sum$ 里面的使用整除分塊，這個整除分塊怎么做呢？
在列舉 $\lfloor\frac{k}{i}\rfloor$ 時，假如一個塊的左區間是 $l$，右區間是 $r$，
因為這一段 $\lfloor\frac{k}{i}\rfloor$ 的值相同，所以設它為 $x$
那么這一段的貢獻就是 $l\cdot x + (l+1)\cdot x + (l+2)\cdot x +...+ r\cdot x$，
把 $x$ 提出來再用等引數列求和公式得到：
$(l + r) * (r - l + 1) / 2 * x$，另外注意 $\lfloor\frac{k}{l}\rfloor=0$ 時除數為 $0$，所以要特判，以及 $r$ 超過 $n$ 的情況，
代碼（當然也是現場寫的）：
int ans = n * k;
for (int l = 1, r; l <= n; l = r + 1) { if (k / l) r = min (n, k / (k / l) );
else break;// k / l 已經等于 0 了，乘上 0 不會對答案產生任何的貢獻， ans -= (r - l + 1) * (l + r) / 2 * (k / l); }
形式二：
給定 $n$，$m$，求 $\sum\limits_{i=1}^{\min(n,m)} \lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor$
由于 $\lfloor\frac{n}{i}\rfloor$ 的取值只有 $2\sqrt{n}$ 種，所以兩者相乘，多了 $2\sqrt{n}$ 個取值，也就 $4\sqrt{n}$ 種，
之前，我們的 $r$ 設為 $n / (n / l)$，現在我們設為 $\min(n/(n / l), m / (m / l))$，代碼如下：
for (int l = 1, r; l <= min (n, m); l = r + 1) { r = min (n / (n / l), m / (m / l) ); ans += (r - l + 1) * (n / l) * (m / l); }
形式三：
求 $\sum\limits_{i=1}^n f(i)\cdot \lfloor\frac{n}{i}\rfloor$，
受形式一的啟發，為 $f$ 函式預處理前綴和，處理答案的時候，還是分配律，
代碼大家可以自己探究一下，
數論分塊例題：
第一題：
$P3935$ $Calculating$：若 $x$ 分解質因數結果為 $x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$，令$f(x)=(k_1+1)(k_2+1)\cdots (k_n+1)$，求 $\sum_{i=l}^rf(i)$ 對 $998\,244\,353$ 取模的結果，
思路：
首先容斥一下，只要求 $1$ ~ $r$ 的 $f$ 和然后減下 $1$ ~ $l-1$ 的就行，
先看 $(k_1+1)(k_2+1)\cdots (k_n+1)$，這個東西其實就是 $x$ 的因數個數，
粗略證明一下：每個 $k$ 次方我們可以選擇 $0$~$k$ 次方乘到數 $t$ 上，
這樣構造的數 $t$ 互不相同且一一對應 $x$ 的因數，
那么就成了 $\sum\limits_{i=1}^n d(i)$，$d(i)$ 表示 $i$ 的因數個數，
再來看怎么求這個，列舉因數 $k$，它在 $1$ ~ $n$ 中成為因數的個數就是 $\lfloor\frac{n}{k}\rfloor$，
$k$ 可以取任意的 $1$ ~ $n$ 的整數，于是就成了：
$\sum\limits_{i=1}^n \lfloor\frac{n}{i}\rfloor$，這不就是數論分塊嗎，$O(\sqrt{n})$ 解決了，別忘了最終答案要 $f(r)-f(l-1)$，
代碼：
#include <iostream> const long long mod = 998244353; using namespace std; long long l, r, x, y; long long f (long long n) { long long ret = 0; l = 1; for (; l != n + 1; l = r + 1) { r = n / (n / l); ret = (ret + (r - l + 1) * (n / l) % mod) % mod; } return ret; } int main () { scanf ("%lld%lld", &x, &y); printf ("%d", ( ( (f (y) - f (x - 1) ) % mod + mod) % mod) ); return 0; }
第二題：
拓展題：$P2260$ 模積和，這個需要用 $1$ ~ $i$ 平方和公式，等引數列求和公式，和超級繁瑣的數論分塊，
想要鉆研的同學們可以去做一下，
代碼：
#include <iostream> const int mod = 19940417, inv6 = 3323403; using namespace std; long long x, y, l, r; long long f (long long n, long long m) {//求解 sum (i = 1 to n) i * 下取整 (m / i) 的值 long long ret = 0; l = 1; for (; l != n + 1; l = r + 1) { if (m / l) r = min (n, m / (m / l) ); else break; ret = (ret + (l + r) * (r - l + 1) / 2 % mod * (m / l) % mod) % mod; } return ret; } long long sum (long long n) {return n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod;} long long fun (long long n, long long m) {//求解 sum (i = 1 to n) i ^ 2 * 下取整 (n / i) * 下取整 (m / i) 的值 long long ret = 0; l = 1; for (; l <= min (n, m); l = r + 1) { r = min (n / (n / l), m / (m / l) ); ret = (ret + (sum (r) - sum (l - 1) ) * (m / l) % mod * (n / l) % mod) % mod; } return ret; } int main () { cin >> x >> y; if (x > y) swap (x, y); cout << ( (x * x % mod - f (x, x) ) * (y * y % mod - f (y, y) ) % mod - (x * x % mod * y % mod - y * f (x, x) % mod - x * f (x, y) % mod + fun (x, y) ) % mod + mod) % mod; return 0; }
一些有用的定義：
數論函式：值域定義在正整數上的函式，
積性函式：對于任何兩個正整數$p$，$q$，都滿足 $\gcd(p,q)=1$ 且 $f(p) \cdot f(q) = f(p\cdot q)$ 的數論函式 $f(n)$，
完全積性函式：對于任何兩個正整數 $p$，$q$，都滿足 $f(p)\cdot f(q)=f(p\cdot q)$ 的數論函式 $f(n)$，
艾弗森括號：形如 $[P]$，其中 $P$ 是一個命題，若為真，則回傳值為 $1$，否則回傳 $0$，
常見的積性函式：
單位函式 $?(n)=[n=1]$，
冪函式 $Id^k(n)=n^k$，$Id^1(n)$ 通常就記為 $Id(n)$，
常值函式 $1(n)=1$，
因數個數函式 $d(n)=\sum\limits_{d|n} 1$
因數 $k$ 次方和函式 $\sigma_k(n)=\sum\limits_{d|n} d^k$，$k=0$ 時為因數個數，$k=1$ 時為因數和，
歐拉函式 $φ(n)=\sum\limits_{i=1}^n [\gcd(i,n)=1]$
莫比烏斯函式 $\mu (n)：$ 分三種情況：
$n=1$：$\mu (n)=1$
$n$ 含有平方因子：$\mu(n)=0$
否則為 $(-1)^k$，$k$ 為 $n$ 不同質因子個數，
如果一個函式是積性函式，那么可以對其線性篩，
這些現在大家可能覺得沒什么用，待會兒就知道了，
狄利克雷卷積：
我們定義兩個數論函式 $f,g$ 在 $n$ 的狄利克雷卷積為：
$(f\times g)(n)=\sum\limits_{d|n} f(d)\cdot g(\frac{n}{d})$
性質滿足交換律，結合律，分配律，
簡單反演：
反演：如果一些數論函式較難求得，但是可以求出它的因數個數，因數和等，可以用反演簡化運算，
目前我知道的反演有兩種：莫比烏斯反演，歐拉反演，
很多題目兩種反演都可以用，下面我們先來介紹一下這兩個的主要內容吧，
莫比烏斯反演：
$[n=1]=\sum\limits_{d|n} \mu(d)$，意思是一個數所有因數的 $\mu$ 和等于這個數是否為 $1$，
更直白的說：如果 $n$ 為 $1$，那么 $\sum\limits_{d|n} \mu(d) = 1$，否則為 $0$，
歐拉反演：
$n=\sum\limits_{d|n} φ(n)$，一個數等于這個數所有因數的 $φ$ 和，證明程序太長，大家請自行 BFS，
例題：
了解了兩種反演后，我們來做幾道例題，
第一題：
求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m \gcd(i,j)$ 模 $998244353$ 的結果，以下全部假設 $n\leq m$，
首先，暴力是 $n^2\log n$ 的，過不了，考慮使用反演，
T1歐拉反演做法：
原式 $=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|i,d|j} φ(d)$，
注意這里如果一個數既是 $i$ 的因數又是 $j$ 的因數，那么它就是 $\gcd(i,j)$ 的因數，
內層回圈和 $d$ 無關，我們可以把 $d$ 弄出來列舉因數得到：
$\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^m [d|i,d|j] φ(d)$，這一步 $d$ 相當于列舉所有 $\gcd(i,j)$ 的因數，
$phi(d)$ 與內層回圈無關，可以用分配律提出來得到：$\sum\limits_{d=1}^n φ(d)\sum\limits_{i=1}^n\sum\limits_{j=1}^m [d|i,d|j]$，
然后發現內兩層回圈就是求倍數個數，很容易求得，$d$ 確定時，$[d|i,d|j]$ 的個數就是 $\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$，
所以原式進一步化為：$\sum\limits_{d=1}^n φ (d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$，使用整除分塊和杜教篩能做到 $n^{\frac{2}{3}}$，
當然，一般題目不會有這么大的資料范圍，線性篩就夠用了，
代碼（內含線性篩 $φ$ 的解釋）：
#include <iostream> #define int long long using namespace std; const int mod = 998244353; int n, m, ans, cnt; bool prime[1000005]; int primes[300005], phi[1000005]; void init () { phi[1] = 1; for (int i = 2; i <= 1000000; i ++){ if (! prime[i]) { primes[++ cnt] = i; phi[i] = i - 1;//i 是質數，1 ~ i - 1 都和它互素 } for (int j = 1; j <= cnt && i * primes[j] <= 1000000; j ++) { prime[i * primes[j] ] = true; if (i % primes[j] == 0) { phi[i * primes[j] ] = phi[i] * primes[j];//i 是 primes[j] 的倍數，此時 phi[i * primes[j] ] = phi[i] * primes[j]， break; } phi[i * primes[j] ] = phi[i] * (primes[j] - 1);//i 和 primes[j] 互素，根據積性函式定義， //phi[i * primes[j] ] = phi[i] * phi[primes[j] ]，即 phi[i] * (primes[j] - 1)， } phi[i] = (phi[i] + phi[i - 1]) % mod;//預處理前綴和 + 取模， } } signed main () { init (); cin >> n >> m; if (n > m) swap (n, m); for (int l = 1, r; l <= n; l = r + 1) {//整除分塊， r = min (n / (n / l), m / (m / l) ); ans = (ans + (phi[r] - phi[l - 1]) * (n / l) % mod * (m / l) % mod) % mod; } cout << ans; return 0; }
T1莫比烏斯反演做法：
$\sum\limits_{d=1}^n d \cdot \sum\limits_{i=1}^n\sum\limits_{j=1}^m [\gcd(i,j)==d]$
若 $\gcd(i,j)=d$，那么 $\gcd(i/d,j/d)=1$，
化為 $\sum\limits_{d=1}^n d\cdot \sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)==1]$
此時使用莫反：$\sum\limits_{d=1}^n d\cdot\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum\limits\sum\limits_{x|i,x|j} \mu(x)$
列舉 $x$ 把 $\mu(x)$ 提出得：$\sum\limits_{d=1}^n d\cdot\sum\limits_{x=1}^m \mu(x) \cdot\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[x|i,x|j]$
內兩層回圈也是求倍數個數，化簡為 $\lfloor\frac{n}{xd}\rfloor\lfloor\frac{m}{xd}\rfloor$
原式化為：$\sum\limits_{d=1}^n d\cdot\sum\limits_{x=1}^{\lfloor\frac{m}{d}\rfloor} \mu(x) \cdot\lfloor\frac{n}{xd}\rfloor\lfloor\frac{m}{xd}\rfloor$，把 $x$ 換成 $T$ 美觀一些：
$\sum\limits_{d=1}^n d\cdot\sum\limits_{T=1}^{\lfloor\frac{m}{d}\rfloor} \mu(T) \cdot\lfloor\frac{n}{Td}\rfloor\lfloor\frac{m}{Td}\rfloor$
線性篩 $\mu$ 然后調和級數 $O(n\log n)$ 可以求得，（默認 $n$，$m$ 同階，列舉 $Td$ 可以轉換成歐拉反演，$O(n)$ 求）
（后面我將不再詳細介紹每一步反演的程序，僅僅選擇重要的幾步介紹，）
線性篩 $\mu$ 的代碼：
#include <iostream> using namespace std; int cnt; int primes[300005], mu[1000005]; bool primes[1000005]; int main () { for (int i = 2; i <= 1000000; i ++) { if (!prime[i]) { primes[++ cnt] = i; mu[i] = -1;//僅有一個質因子，它本身，注意：1不是質數， } for (int j = 1; j <= cnt && i * primes[j] <= 1000000; j ++) { prime[i * primes[j] ] = true; if (i % primes[j] == 0) { mu[i * primes[j] ] = 0;//含有平方因子 primes[j] * primes[j]， break; } mu[i * primes[j] ] = -mu[i];//多了一個因子 primes[j]，乘上 -1，或者根據積性函式的定義， } } return 0; }
第二題：
$2.$ 求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m [\gcd(i,j)==1]$
這題貌似只能用莫比烏斯反演，大家可以先自己嘗試一下，這個比較簡單，
T2莫比烏斯反演做法：
$\sum\limits_{i=1}^n\sum\limits_{j=1}^m [\gcd(i,j)==1]$，以下設 $n<m$
$=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|i,d|j} \mu(d)$
$=\sum\limits_{d=1}^n\mu(d)\cdot \sum\limits_{i=1}^n\sum\limits_{j=1}^m [d|i,d|j]$
$=\sum\limits_{d=1}^n\mu(d)\cdot \lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$
預處理 $\mu$ 前綴和 $O(n)$ 加整除分塊單次 $\sqrt{n}$，
（可能大家覺得整除分塊可以不用，因為時間復雜度瓶頸在線性篩，但是學了杜教篩之后，這題的資料范圍就可以到 $10^{10}$ 卡線性篩）
第三題：
$3.$ 求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m f(\gcd(i,j) )$，其中 $f$ 是數論函式，
這題也不能用歐拉反演做，因為 $f$ 是個函式，并不知道因數個數，只能列舉 $\gcd$
T3莫比烏斯反演做法：
$\sum\limits_{i=1}^n\sum\limits_{j=1}^m f(\gcd(i,j) )$
$=\sum\limits_{d=1}^n f(d)\cdot\sum\limits_{i=1}^n\sum\limits_{j=1}^m [\gcd(i,j)==d]$
$=\sum\limits_{d=1}^n f(d)\cdot\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)==1]$
$=\sum\limits_{d=1}^n f(d)\cdot\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum\limits_{x|i,x|j}\mu(x)$
$=\sum\limits_{d=1}^n f(d)\sum\limits_{x=1}^{\lfloor\frac{n}{d}\rfloor}\mu(x) \cdot\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[x|i,x|j]$
$=\sum\limits_{d=1}^n f(d)\sum\limits_{x=1}^{\lfloor\frac{n}{d}\rfloor}\mu(x) \cdot\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor$
列舉 $dx$，令其 $=T$ 得：
$=\sum\limits_{T=1}^n\sum\limits_{x|T} f(\frac{T}{x})\cdot \mu(x)\cdot\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$
內層 $\sum$ 提出來，
$=\sum\limits_{T=1}^n \lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum\limits_{x|d}f(\frac{T}{x})\cdot \mu(x)\cdot$
然后發現是個狄利克雷卷積，
$=\sum\limits_{T=1}^n \lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor (f\cdot \mu) (T)$
預處理 $O(n)$ 加整除分塊單次詢問 $\sqrt{n}$，
第四題：
P3327 [SDOI2015]約數個數和
設 $d(x)$ 為 $x$ 的約數個數，給定 $n,m$，求 $\sum_{i=1}^n\sum_{j=1}^md(i\cdot j)$，
我會盡量寫的詳細些，
$\sum\limits_{i=1}^n\sum\limits_{j=1}^m d(i\cdot j)$（$n < m$）
$=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \sum\limits_{x|i}\sum\limits_{y|j} [\gcd(x,y)=1]$（特殊性質，證明看那題的題解）
$=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \sum\limits_{x=1}^n\sum\limits_{y=1}^m[x|i,y|j,\gcd(x,y)=1]$
$=\sum\limits_{x=1}^n\sum\limits_{y=1}^m \sum\limits_{i=1}^n\sum\limits_{j=1}^m[x|i,y|j,\gcd(x,y)=1]$
$=\sum\limits_{x=1}^n\sum\limits_{y=1}^m \lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor[\gcd(x,y)=1]$
$=\sum\limits_{x=1}^n\sum\limits_{y=1}^m \lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\sum\limits_{d|x,d|y}\mu(d)$
$=\sum\limits_{d=1}^n\sum\limits_{x=1}^n\sum\limits_{y=1}^m\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor[d|x,d|y]\cdot \mu(d)$
$=\sum\limits_{d=1}^n\mu(d)\sum\limits_{x=1}^n\sum\limits_{y=1}^m\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor[d|x,d|y]$
列舉 $x$ $y$，改為列舉 $x\cdot d$，$y\cdot d$，這個一定被 $d$ 整除，可以去掉這個棘手的條件了，
$=\sum\limits_{d=1}^n\mu(d)\sum\limits_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{xd}\rfloor\lfloor\frac{m}{dy}\rfloor$
$=\sum\limits_{d=1}^n\mu(d)(\sum\limits_{x=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{xd}\rfloor\cdot\sum\limits_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{dy}\rfloor)$
大家可能還沒發現后面可以用整除分塊，我們令 $n'=\lfloor\frac{n}{d}\rfloor$，$m'=\lfloor\frac{m}{d}\rfloor$，
這下一目了然，$=\sum\limits_{d=1}^n\mu(d)(\sum\limits_{x=1}^{n'} \lfloor\frac{n'}{x}\rfloor\cdot \sum\limits_{y=1}^{m'} \lfloor\frac{m'}{y}\rfloor)$，
注意這里 $\sum\limits_{x=1}^{n'} \lfloor\frac{n'}{x}\rfloor\cdot \sum\limits_{y=1}^{m'} \lfloor\frac{m'}{y}\rfloor$ 和 $\sum\limits_{x=1}^{n'} \lfloor\frac{n'}{x}\rfloor \sum\limits_{y=1}^{m'} \lfloor\frac{m'}{y}\rfloor$ 的區別：一個是兩者相乘，另一個是 $\sum$ 套 $\sum$，
我們再來講一下這個東西怎么整除分塊：$n'=\lfloor\frac{n}{d}\rfloor$，$m'=\lfloor\frac{m}{d}\rfloor$，不難發現大量 $n'$，$m'$ 相同，內層還有一個整除分塊，
這時有兩個選擇，兩層整除分塊：$n^{\frac{3}{4}}$
預處理 $n=1$ ~ $50000$ 時，$\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor$，
怎么預處理呢？我們發現 $\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor=\sum\limits_{i=1}^n d(i)$，這個在整除分塊例題的時候證明過，線性篩 $d$ 函式就行了，
預處理 $\mu$，$d$ 函式的前綴和 $O(n)$ 再加上整除分塊單次詢問 $O(\sqrt{n})$，可以通過此題，
代碼（內含線性篩 $d$ 函式的解釋）：
#include <iostream> #define int long long using namespace std; int T, n, m; int ans, cnt; int mu[50005], num[50005], sigma[50005], primes[20005];//num[i] 表示 i 最小質因子的數量，看到后面注釋就能明白為什么需要 bool prime[50005]; void init () { mu[1] = sigma[1] = 1; for (int i = 2; i <= 50000; i ++) { if (!prime[i]) { primes[++ cnt] = i; sigma[i] = 2;//素數有兩個約數，它本身和 1 mu[i] = -1; num[i] = 1; } for (int j = 1; j <= cnt && i * primes[j] <= 50000; j ++) { prime[i * primes[j] ] = true; if (i % primes[j] == 0) { mu[i * primes[j] ] = 0;//有平方因子 sigma[i * primes[j] ] = sigma[i] / (num[i] + 1) * (num[i] + 2); /*設 i 被分解后各項的次方分別是：a_1,a_2,a_3...a_n，（底數從小到大排列的） 在整除分塊例題中證明過 d[i] = (a_1 + 1) * (a_2 + 1) * ... * (a_n + 1) 現在多了一個最小質因數，d[i * primes[j] ] = (a_1 + 2) * (a_2 + 1) * ... * (a_n + 1) 所以我們需要記錄 a_1，也就是最小質因子的數量， */ num[i * primes[j] ] = num[i] + 1;//那么最小質因子的數量顯然加上一 break; } mu[i * primes[j] ] = -mu[i]; sigma[i * primes[j] ] = sigma[i] * 2;//i 所有的因子乘上 primes[j] 可以構造出新的因子， num[i * primes[j] ] = 1;//primes[j] 是 i * primes[j] 的最小質因數， //而 i % primes[j] != 0，所以 num[i * primes[j] ] = 1 } sigma[i] += sigma[i - 1];//預處理前綴和 mu[i] += mu[i - 1]; } } int f (int x) {return sigma[x];}//求解 Σ下取整 (x/i)，根據剛剛的推論，它就等于 sigma[1] +... + sigma[x] signed main () { init (); scanf ("%lld", &T); while (T --) { ans = 0; scanf ("%lld%lld", &n, &m); if (n > m) swap (n, m); for (int l = 1, r; l <= n; l = r + 1) {//整除分塊 r = min (n / (n / l), m / (m / l) ); ans += (mu[r] - mu[l - 1]) * f (n / l) * f (m / l); //這一段 n' m' 的值是一樣的，可以把 mu 提出來用前綴和， } printf ("%lld\n", ans); } return 0; }
總結：
反演時通常考慮列舉一個數，然后快速求出因數個數啥的；
如果不能繼續反演，可以考慮列舉兩個數相乘啥的，就能從絕境中走出，
反演時兩種都試一下，選擇最好寫，時間復雜度合適的演算法，
杜教篩：
杜教篩也是反演的基礎，我們先來了解一下它吧，
介紹：
杜教篩三問：名字怎么來的？有什么用？時間復雜度如何？
$1.$ 由一位姓杜的學長初次在國內使用并傳開，后參考他的名字命名這個演算法，
$2.$ 可以在非線性時間內求解積性函式 $f$ 前 $n$ 項的和，
$3.$ 不加預處理，時間復雜度 $O(n^\frac{3}{4})$，加上預處理 $O(n^\frac{2}{3})$，
（大家可能覺得 $n^{\frac{1}{3}}$ 和 $O(n)$ 差距很小，事實上，在 $n=2^{31}$ 時，兩者相差將近 $1300$ 倍！）
例題：
P4213 【模板】杜教篩（Sum）
給定一個正整數，求：$ans_1=\sum_{i=1}^n φ(i)$，$ans_2=\sum_{i=1}^n \mu(i)$
我們一邊講題一邊介紹杜教篩吧，
考慮構造數論函式使 $f\times g = h$，并且設我們要求的函式是 $f$ 的前綴和，嘗試化簡它，
$\sum\limits_{i=1}^n\sum\limits_{d|i} g(d)f(\frac{n}{d})= \sum\limits_{i=1}^n h(i)$
列舉 $d$ 得：$\sum\limits_{d=1}^n g(d)\sum\limits_{i=1}^n [d|i]f(\frac{i}{d})$
內層 $\sum$ 可以化簡，列舉 $id$，$\sum\limits_{d=1}^n g(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} f(i)$
所以 $\sum\limits_{d=1}^n g(d) \sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} f(i)=\sum\limits_{i=1}^n h(i)$
然后把 $d=1$ 時拆開得到：$g(1)\sum\limits_{i=1}^n f(i) + \sum\limits_{d=2}^n g(d) \sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} f(i)=\sum\limits_{i=1}^n h(i)$
設 $s(i)=f(1)+f(2)+...+f(i)$
又化簡為 $s(n)g(1) + \sum\limits_{d=2}^n g(d) s(\lfloor\frac{n}{d}\rfloor)=\sum\limits_{i=1}^n h(i)$
所以 $s(n)=\frac{\sum\limits_{i=1}^n h(i) - \sum\limits_{d=2}^n g(d) s(\lfloor\frac{n}{d}\rfloor)}{g(1)}$，這個就是杜教篩公式了，
后面可以整除分塊，前面 $h$ 函式前綴和我們只要構造 $O(\sqrt{n})$ 以內可求前綴和的 $h$ 函式就行了（瓶頸在后面的 $\sqrt{n}$），
加上記憶化，時間復雜度為 $n^\frac{3}{4}$，預處理 $k$ 以內的 $s$ 便可做到 $T(n)=O(k)+O(\frac{n}{\sqrt{k}})$，$k$ 取 $n^\frac{2}{3}$ 時最優，時間復雜度為 $n^\frac{2}{3}$，
求 $φ$ 前 $n$ 項和：
取 $g=1$ （常值函式 $1(n)=1$），因為 $f$ 是 $φ$ 函式，根據歐拉反演，$φ\times 1 = Id^1$，所以 $h=Id^1$，這些都很好求，
帶回得到 $s(n)=\frac{\sum\limits_{i=1}^n i - \sum\limits_{d=2}^n (s(\lfloor\frac{n}{d}\rfloor)\cdot 1)}{1}$，
進一步化簡得到：$s(n)=\frac{(n + 1)\cdot n}{2} - \sum\limits_{d=2}^n s(\lfloor\frac{n}{d}\rfloor)$，
代碼：
int sum_phi (int n) {//求 s(n) 的值 if (n <= b) return s[n];//提前篩好的 if (map[n]) return map[n];//記憶化 int ans = n * (n + 1) / 2; for (int l = 2, r; l <= n; l = r + 1) {//整除分塊 r = n / (n / l); ans -= sum_phi (n / l) * (r - l + 1); } return map[n] = ans;//記憶化 }
求 $\mu$ 前 $n$ 項和：
依然取 $g=1$，$f$ 當然取 $\mu$ 函式，根據莫比烏斯反演，$\mu \times 1 = ?$，所以 $h=?$，也很好求，
化簡為 $s(n)=1-\sum\limits_{d=2}^n s(\lfloor\frac{n}{d}\rfloor)$，
int sum_mu (int n) { if (n <= b) return s[n]; if (map[n]) return map[n]; int ans = 1; for (int l = 2, r; l <= n; l = r + 1) { r = n / (n / l); ans -= sum_phi (n / l) * (r - l + 1) / 2; } return map[n] = ans;//記憶化 }
例題：
恭喜你已經學完了大部分反演的內容，我們做幾道例題，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/549144.html
標籤：其他
下一篇：【ACM演算法競賽日常訓練】DAY10題解與分析【月月給華華出題】【華華給月月出題】| 篩法 | 歐拉函式 | 數論