本來沒有學習這種較難的算法的想法的，因為比賽也做不到這種難度的題， 但是最近打牛客多校02，有一題要求 $[1,n]$ 中素數的個數，我以為是像莫反一樣容斥，但是后面感覺不行。賽后知道是用 min_25 篩來求，賽時過了一車，因此我也不得不學習這個算法了。

我打算拿洛谷里面的模板來舉例。

就是給你積性函數
$$f(x)=?\begin{array}{ll}k& x=1\\ g(x)={\sum }_{i=0}^k{a}_i{x}^i& x=p^c,p\in prime,c\ge 1\\ f(x_1)f(x_2)& (x_1,x_2)=1\end{array}$$

然后讓你求
$$\sum _{i=1}^{n}f(i)$$

其中 $n\le 10^{13}$

在牛客多校的那個題中，也有 $n\le 10^9$

一般來講，想解決這種問題都要從 $i$ 最小的質因子入手，因為一個數要么是質數，要么最小的質因子 $\le n^{0.5}$，而 $n^{0.5}$ 一般都是$10^6$~$10^7$ 數量級，可以直接用線性篩得到，也能全部枚舉一次。因此總的思路大概就是先求出 ${\sum }_{i=1}^{n}g(i)$ 然后通過枚舉最小的質因子來修正有超過一個質因子的數的貢獻，這樣能夠很好的解決大質數無法直接得到的問題。

如果沒有學過要怎么求 ${\sum }_{i=1}^n{i}^k$，可以看我的博客

基于這個大的思路，我自己感覺 min_25 篩的思路是非常自然，很容易就能記下來。

對于式子
$$\sum _{i=1}^{n}f(i)$$

先將 $1$ 去掉，因為其不包含任何素數，計算的時候容易出現奇怪的錯誤，雖然按照積性函數的定義， $f(1)=1$。

于是變成
$$f(1)+\sum _{i=2}^{n}f(i)$$

自己感覺 min_25 篩很關鍵的一點是其能夠快速求出
$$g(b)=\sum _{p\in prime,p\le b}{p}^k$$其中 $b=?\frac{n}{a}?$，這也意味著 $b$ 的個數只有 $O(n^{0.5})$

雖然只能求出若干次方的和，但只要把每一項都求一次就可以得到原函數了。

然后剩下的和數就能通過枚舉小最小的質因子來考慮

因此 min_25 篩有兩步，分別是求出質數出的函數和，求出所有的函數和

第一步：求出質數處的函數和

這一步的思路就是像我剛才說的，先求出所有的函數和，然后通過枚舉最小的質因子把和數的貢獻剪掉即可。

我們從小到大枚舉素數，并且同時維護所有的 $g(b)$，假設當前的素數為 $p$，假設其為第 $i$ 個素數。那么顯然有 $p\le n^{0.5}$。 我們記第 $i$ 個素數為 $p_i$

對于 $g(b)$，我們應該減去 $1$ ~ $b$ 中最小質因子為 $p$ 的和數，如果我們直接固定 $p$，也就是只需要考慮 $1$ ~ $?\frac{b}{p}?$ 中最小質因子 $\ge p$ 的數，然后你就會發現這個數剛好就是 $g(?\frac{b}{p}?)?{\sum }_{j=1}^{i?1}{p}_j^k$，（因為 $g$ 函數中包含 $<p$ 的素數）后者只需要線性篩的時候預處理即可。

然后容斥完以后我們就可以得到所有的 $g(b)$ 了。

第二步：求出原函數

這一步的思路是也是拆分成質數貢獻與和數貢獻，質數貢獻可以直接通過前面的 $g$ 函數得到，和數貢獻可以通過枚舉最小質因子不斷遞歸求解。

我們另 $S(n,x)$ 表示 $1$ ~ $n$ 中最小質因子 $>p_x$ 的數的貢獻之和，我們認為質數本身就是其最小質因子。

然后有
$$S(n,x)=g(n)?\sum _{i=1}^{x}f(p_i)+\sum _{p_i^c\le n,i>x}f(p_i^c)(S(?\frac{n}{p_i^c}?,i+1)+[c>1])$$

因為 $c>1$ 的時候 $p_i^c$ 本身也能夠產生貢獻。

以下是我洛谷模板的代碼

#include <bits/stdc++.h>
#define ll long long
using namespace std;const int mod = 1e9 + 7;int power(int a, int b) {int ret = 1;while (b) {if (b & 1) ret = 1ll * ret * a % mod;a = 1ll * a * a % mod; b >>= 1;}return ret;
}const int inv2 = power(2, mod - 2), inv3 = power(3, mod - 2);
const int N = 1e6 + 10;int cnt, p[N]; bool v[N];
int sp1[N], sp2[N];
ll n, Sqr, w[N];
int tot, g1[N], g2[N], ind1[N], ind2[N];void pre(int n) {v[1] = 1;for (int i = 2; i <= n; i++) {if (!v[i]) {p[++cnt] = i;sp1[cnt] = (sp1[cnt - 1] + i) % mod;sp2[cnt] = (sp2[cnt - 1] + 1ll * i * i) % mod;}for (int j = 1; j <= cnt && i * p[j] <= n; j++) {v[i * p[j]] = 1;if (i % p[j] == 0) break;}}
}int S(ll x, int y) {if (p[y] >= x) return 0;ll k = x <= Sqr ? ind1[x] : ind2[n / x];int ans = (1ll * g2[k] - g1[k] + mod - (sp2[y] - sp1[y]) + mod) % mod;for (int i = y + 1; i <= cnt && 1ll * p[i] * p[i] <= x; i++) {ll pe = p[i];for (int e = 1; pe <= x; e++, pe *= p[i]) {ll xx = pe % mod;ans = (ans + xx * (xx - 1) % mod * (S(x / pe, i) + (e != 1)) % mod) % mod;}}return ans % mod;
}int main() {// freopen("in.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;Sqr = sqrt((long double)n);pre(Sqr);for (ll i = 1, j; i <= n; i = j + 1) {j = n / (n / i);w[++tot] = n / i;int now = w[tot] % mod;g1[tot] = 1ll * now * (now + 1) / 2 % mod - 1;g2[tot] = 1ll * now * (now + 1) / 2 % mod * (2 * now + 1) % mod * inv3 % mod - 1;if (n / i <= Sqr) ind1[n / i] = tot;else ind2[n / (n / i)] = tot;}for (int i = 1; i <= cnt; i++) {for (int j = 1; j <= tot && 1ll * p[i] * p[i] <= w[j]; j++) {ll k = w[j] / p[i] <= Sqr ? ind1[w[j] / p[i]] : ind2[n / (w[j] / p[i])];g1[j] = (g1[j] - 1ll * p[i] * (g1[k] - sp1[i - 1] + mod) % mod + mod) % mod;g2[j] = (g2[j] - 1ll * p[i] * p[i] % mod * (g2[k] - sp2[i - 1] + mod) % mod + mod) % mod;}}cout << (S(n, 0) + 1) % mod << "\n";return 0;
}

時間復雜度

第一步的時間復雜度是 $O(\frac{n^{0.75}}{\ln n})$ 是沒有爭議的，有一些人底下寫的是 $\log$ 也是對的，因為只有常數倍的差別

對于第一重循環，因為素數的密度的是 $\frac{1}{\ln n}$，所以可以提出一個 $\frac{1}{\ln n}$

然后變為這個式子 $O({\sum }_{i=1}^{\sqrt{n}}\sqrt{i}+\sqrt{\frac{n}{i}})=O({\sum }_{i=1}^{\sqrt{n}}\sqrt{\frac{n}{i}})=O(\sqrt{n}{\sum }_{i=1}^{\sqrt{n}}\sqrt{\frac{1}{i}})=O(\sqrt{n}{\int }_1^n\frac{1}{\sqrt{x}}dx)=O(\sqrt{n}\sqrt{n}{|}_1^{\sqrt{n}})=O(n^{0.75})$

第二步我在網上沒有找到具體的證明，自己也感覺比較難證明，但是聽說是一般情況是 $O(n^{1?\delta })$，但是如果 $n\le 10^{13}$，就滿足 $O(\frac{n^{0.75}}{\ln n})$，基本適合OI的范圍。

學完 min_25 篩，就會發現前面那個求素數個數的問題實在是太簡單了，連 $S$ 函數都不用算，直接把 $g$ 函數計算以下就行了，然后把多項式設置為 $f(x)=1$ 即可。