本文共 3319 字，大约阅读时间需要 11 分钟。
Min_25筛法是一种高效的筛法，主要用于计算积性函数 ( f(i) ) 的前缀和。它的复杂度为 ( O(n^{\frac{3}{4}} / \log n) )，在数论和算法优化领域备受关注。与传统的埃筛法不同，Min_25筛法通过递推的方法，能够更高效地计算函数的前缀和。
Min_25筛法的核心原理
Min_25筛法的关键在于定义两个辅助函数 ( g(n, j) ) 和 ( S(n, j) )：
( g(n, j) )：表示从质数集 ( P ) 开始，考虑第 ( j ) 个质数 ( P_j ) 的贡献。它的递推公式如下：[g(n, j) =\begin{cases}g(n, j-1) & \text{当 } P_j^2 > n \g(n, j-1) - f(P_j) \left( g\left( \left\lfloor \frac{n}{P_j} \right\rfloor, j-1 \right) - \sum_{i=1}^{j-1} f(P_i) \right) & \text{当 } P_j^2 \leq n\end{cases}]这个公式的意义是：如果当前质数 ( P_j ) 的平方大于 ( n )，则 ( g(n, j) ) 与 ( g(n, j-1) ) 相等；否则，需要调整 ( g(n, j) ) 以反映 ( P_j ) 的贡献。
( S(n, j) )：表示从质数集 ( P ) 开始，计算到第 ( j ) 个质数的总和。最终，我们需要计算 ( S(n, 1) + 1 ) 来得到最终结果。
Min_25筛法的实现
Min_25筛法的实现通常包括以下几个步骤：
预处理质数：首先需要预处理所有小于等于 ( \sqrt{n} ) 的质数。这些质数将用于筛法的递推过程。
初始化数组：创建必要的数组如 ( f )、( p )、( id1 )、( id2 ) 等，用于存储质数、索引和其他辅助信息。
递归计算 ( g ) 和 ( h )：通过对每个质数 ( P_j ) 进行递归计算，更新 ( g ) 和 ( h ) 数组，反映当前质数的贡献。
计算最终结果：最终结果通过 ( S(n, 1) + 1 ) 得到，其中 ( S(n, 1) ) 是从质数集 ( P ) 开始的总和。
代码实现示例
以下是 Min_25筛法 的一个代码实现示例：
#include#include #include #include #include #define maxn 300005#define re register#define LL long longconst LL mod = 1000000007;const LL inv2 = 500000004;LL n;LL w[maxn], Sqr, tot;LL p[maxn], pre[maxn], id1[maxn], id2[maxn], h[maxn], g[maxn], m;int f[maxn];inline LL S(LL x, int y) { if (x <= 1 || p[y] > x) return 0; int k = (x <= Sqr) ? id1[x] : id2[n / x]; LL ans = (h[k] - g[k] - pre[y - 1] + y - 1 + ((y == 1) ? 2LL : 0)) % mod; ans = (ans + mod) % mod; for (re int k = y; k <= tot && p[k] * p[k] <= x; k++) { LL p1 = p[k]; for (re int e = 1; p1 <= x; e++, p1 *= p[k]) { LL x_div = x / p1; ans += (1LL * (S(x_div, k + 1) + ((e > 1) ? 1LL : 0)) * pow(p[k], e) % mod) % mod; ans %= mod; } } return ans;}int main() { scanf("%lld", &n); Sqr = std::sqrt(n) + 1; f[1] = 1; for (re int i = 2; i <= Sqr; i++) { if (!f[i]) { p[++tot] = i; pre[tot] = (pre[tot - 1] + i) % mod; } for (re int j = 1; j <= tot && p[j] * i <= Sqr; j++) { f[p[j] * i] = 1; if (i % p[j] == 0) break; } } for (re LL l = 1, r = n; l <= n; l = r + 1) { r = n / (n / l); w[++m] = n / l; if (w[m] <= Sqr) { id1[w[m]] = m; } else { id2[n / w[m]] = m; } g[m] = (w[m] - 1) % mod; h[m] = ((w[m] + 2LL) % mod) * ((w[m] - 1LL) % mod) % mod; h[m] = (h[m] * inv2) % mod; } for (re int j = 1; j <= tot; j++) { for (re int i = 1; i <= m && p[j] * p[j] <= w[i]; i++) { int k = (w[i] / p[j] <= Sqr) ? id1[w[i] / p[j]] : id2[n / (w[i] / p[j])]; g[i] = (g[i] - g[k] + j - 1LL) % mod; g[i] = (g[i] + mod) % mod; h[i] = (h[i] - (h[k] - pre[j - 1] + mod) % mod * p[j] % mod + mod) % mod; } } printf("%lld\n", 1 + S(n, 1)); return 0;}
示例解释
假设我们需要计算 ( f(i) ) 的前缀和，其中 ( f(i) = i )（即 ( f(i) = i )）。我们可以使用上述代码来实现 Min_25筛法。
预处理质数：首先，代码会预处理所有小于等于 ( \sqrt{n} ) 的质数，并将它们存储在数组 ( p ) 中。
初始化数组：数组 ( id1 ) 和 ( id2 ) 用于快速定位质数范围内的数。
计算 ( g ) 和 ( h )：通过递推公式计算 ( g ) 和 ( h ) 数组，反映每个质数的贡献。
计算最终结果：最终结果通过 ( 1 + S(n, 1) ) 得到，其中 ( S(n, 1) ) 是从质数集开始的总和。
这种方法通过递归的方式，避免了传统埃筛法的线性复杂度，显著提高了计算效率。
发表评论
最新留言
关于作者
