合数 n 的最大真因数是 n 除以它的最小质因子,于是求区间内合数按最小质因子分组后的商之和,用 min_25 筛在 O(n^{3/4}/log n) 内算出前缀和再作差。
OJ: roj
题目 ID: 1804
难度:提高+/省选-
标签:数学数论筛法Min_25 筛python
创建: 2026-10-08 04:13
更新: 2026-10-08 04:13
形式化题目
给定正整数
数据范围:
正解
思路
先化简单个合数。 若
朴素做法与瓶颈。 最直接的是线性筛(欧拉筛)预处理出
关键观察:最小质因子的种类极少。 合数
于是把合数按最小质因子分组来数:对固定的质数
(
到这里问题变成:对每个
用埃氏筛 DP 把"剩下的和"滚出来。 令
(减去
只有
答案怎么取。 把上面的求和式代进去:对每个
这也是实现里直接 ans += d(
状态只有 g1[i]
(此时 g2[w];
查询
为什么是
实现要点。 三条容易踩的坑:
- 必须用高精度整数。
的初值是 ,先算 的话 时约 ,直接超出 64 位;即使按 先除后减, 结果 也已接近 unsigned long long上限、且远超市面上long long的。所以本题的 main.cpp里g1、g2、ans、sp全用__int128, 最后手写 128 位输出。答案本身最大只有(即样例 5 风格的点), 落在 long long内,但中间量不落在,所以不能省。 g2必须倒序更新。 转移要读,而 。 g2按下标递增访问,所以从大到小扫,读到的才是上一阶段的旧值;g1是递减的,从小 往大 扫, 对应的 下标更大、还没被更新,天然安全。 直接返回 0。 此时区间里没有合数; 时 也要能吃下。
说明:本题在仓库素材源(
new_ROJ/problems/1804/)里带有自造数据生成脚本data.py与config.json,data/是据此生成的 10 个点,题面文本与"信息学奥赛一本通·高手训练篇" 同源(该题即 FJWC2018 / BZOJ 5244《最大真因数》)。因此数据规模与官方原题可能不完全一致, 题解以本仓库data/为准。素材里的std.cpp与本文结论一致(同样按最小质因子分组做 min_25 筛), 但它用__int128存全部状态且在处累加贡献,本文的 main.cpp是独立实现。
代码
Python 短解法:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 04:13
# update_at: 2026-10-08 04:13
import sys
from itertools import accumulate
from math import isqrt
type Primes = list[int] # 不超过 sqrt(N) 的质数,升序
type Prefix = list[int] # sp[j] = 前 j 个质数之和
def build_primes(limit: int) -> tuple[Primes, Prefix]:
"""线性筛出 [2, limit] 的质数,并给出质数前缀和。"""
comp = bytearray(limit + 1)
primes: Primes = []
for i in range(2, limit + 1):
if not comp[i]:
primes.append(i)
for p in primes: # 线性筛:每个合数只被最小质因子划去
if i * p > limit:
break
comp[i * p] = 1
if i % p == 0:
break
return primes, [0, *accumulate(primes)]
def comp_sum(n: int) -> int:
"""返回 [1, n] 内所有合数的最大真因数之和。
合数 c 的最大真因数 = c / spf(c)(spf 为最小质因子)。按 spf=p 把合数分组后,
第 p 组的贡献 Σm 恰好是 min_25 筛里被 p 划去的那些数之和再除以 p,
所以只需要滚动维护 g[w] = 「质数或最小质因子 > 已筛质数」的 2..w 数值和。
"""
if n < 4:
return 0 # 1、2、3 都不是合数
S = isqrt(n)
primes, sp = build_primes(S)
# 状态值 val = floor(n/i) 只会取 2*sqrt(n) 个值:val > S 的按 i 存进 g1,
# val <= S 的直接拿 val 当下标存进 g2;i = 1..n//(S+1) 恰好覆盖所有 val > S。
L = n // (S + 1)
g1 = [0, *[(n // i) * (n // i + 1) // 2 - 1 for i in range(1, L + 1)]]
g2 = [x * (x + 1) // 2 - 1 for x in range(S + 1)]
ans = 0
for j, p in enumerate(primes, 1):
pre = sp[j - 1] # 小于 p 的质数之和,即 g 里要留下的质数部分
p2 = p * p
for i in range(1, min(L, n // p2) + 1): # 只有 val >= p^2 的状态才含 p 的倍数
k = i * p # 状态 n//i 除以 p 之后对应 floor(n/k)
cur = g1[k] if k <= L else g2[n // k]
d = cur - pre
if i == 1:
ans += d # 状态 n:最小质因子恰为 p 的合数贡献 Σm
g1[i] -= d * p
for x in range(S, p2 - 1, -1): # 倒序保证读到的是上一阶段的 g2[x//p]
g2[x] -= (g2[x // p] - pre) * p
return ans
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
l, r = next(data), next(data)
print(comp_sum(r) - comp_sum(l - 1)) # 前缀和作差,区间内每个合数贡献不变
if __name__ == "__main__":
solve()C++ 正式解:
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 04:13
* update_at: 2026-10-08 04:13
*/
// 一本通 1804《最大真因数》
// 合数 n 的最大真因数 = n / spf(n)(spf 为最小质因子),因为拿掉最小质因子后剩下的商最大。
// 于是答案 = F(r) - F(l-1),其中 F(N) = Σ_{合数 c<=N} c / spf(c)。
// min_25 筛取权值 f(x)=x 求 F:把合数按最小质因子 p_j 分组,第 j 组是 n = p_j*m
// (m ∈ [p_j, N/p_j] 且 spf(m) >= p_j),每组贡献恰是 Σm,正是筛过程中被 p_j 划去的那些数除以 p_j 的和。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int MAXS = 100005; // sqrt(5*10^9) ≈ 70710,留足余量
bool vis[MAXS]; // 线性筛的合数标记
ll prime[MAXS]; // prime[1..tot]:不超过 sqrt(N) 的质数,升序
lll sp[MAXS]; // sp[j] = 前 j 个质数之和(即「小于 p_{j+1} 的质数和」)
lll g1[MAXS]; // 大状态:下标 i=1..L,状态值 val = n/i > sqrt(n)
lll g2[MAXS]; // 小状态:下标就是状态值 x <= sqrt(n)
int tot; // 质数个数
// 精确求 floor(sqrt(n)):先浮点开方再整数修正(n <= 5*10^9)
ll isqrt_ll(ll n) {
ll x = sqrtl((long double)n);
while (x > 0 && x * x > n) --x;
while ((x + 1) * (x + 1) <= n) ++x;
return x;
}
// 线性筛出 [2, lim] 的质数,并递推前缀和 sp
void build_prime(ll lim) {
tot = 0;
for (ll i = 0; i <= lim; i++) vis[i] = false;
for (ll i = 2; i <= lim; i++) {
if (!vis[i]) {
prime[++tot] = i;
sp[tot] = sp[tot - 1] + i;
}
for (int j = 1; j <= tot && i * prime[j] <= lim; j++) {
vis[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
}
// g[i] 的含义:状态值 w 下「质数 或 最小质因子 > 已筛质数」的所有数值和。
// 初始(一个质数都没筛)就是 2..w 的数值和 w(w+1)/2 - 1。
// 筛 p 时被划去的数是 p*m(m >= p 且 spf(m) >= p),其和 = p*(g(w/p) - sp[小于p的质数和])。
// 状态只有 floor(N/i) 这 2*sqrt(N) 个:值 > S 的按 n/i 存进 g1,值 <= S 的直接用值当下标存 g2。
// F(n) = Σ_{合数 c<=n} c / spf(c)
lll F(ll n) {
if (n < 4) return 0; // 1、2、3 都不是合数
ll S = isqrt_ll(n);
build_prime(S);
ll L = n / (S + 1); // 大状态个数:状态值 n/i > S 的 i 恰好是 1..L
for (ll i = 1; i <= L; i++) {
lll v = n / i;
g1[i] = v * (v + 1) / 2 - 1;
}
for (ll x = 1; x <= S; x++) {
lll v = x;
g2[x] = v * (v + 1) / 2 - 1;
}
lll ans = 0;
for (int j = 1; j <= tot; j++) {
ll p = prime[j], p2 = p * p;
lll pre = sp[j - 1]; // 小于 p 的质数之和
ll hb = min(L, n / p2); // 大状态里值 >= p^2 的个数,更小的状态无 p 的倍数可划
for (ll i = 1; i <= hb; i++) {
ll id = i * p; // 状态值 n/i 再除以 p,即 floor(n/(i*p))
lll cur = (id <= L) ? g1[id] : g2[n / id];
lll d = cur - pre;
if (i == 1) ans += d; // i==1 是状态 n:最小质因子恰为 p 的合数贡献 Σm
g1[i] -= d * p;
}
// 小状态倒序处理,保证读到的 g2[x/p] 还是上一阶段的值(x/p < x 未被本轮更新)
for (ll x = S; x >= p2; x--) g2[x] -= (g2[x / p] - pre) * p;
}
return ans;
}
// 输出 128 位整数:逐位取余打印
void print_lll(lll x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) print_lll(x / 10);
putchar('0' + (int)(x % 10)); // 取值必在 0..9,转成 int 才能参与字符运算
}
int main() {
ll l, r;
if (scanf("%lld %lld", &l, &r) != 2) return 0;
print_lll(F(r) - F(l - 1));
putchar('\n');
return 0;
}复杂度
- 时间:
,其中 ;常数部分是 个状态上的 埃氏筛转移。 时实际转移数百万次,C++ 实测 < 30 ms, Python 实测约 1.2 s(本题允许 Python 慢,算法与 C++ 同阶,未做任何降级)。 - 空间:
。 时状态数 , 质数表 7004 个,共计几 MB,远低于 512 MB。
总结
- 先把"最大真因数"翻译成
,题目里"真因数""最大"这些字眼就没有了, 剩下的只是一个关于最小质因子的求和。 - 计数对象从"数"换成"最小质因子":合数只有
以内的质数那么多种最小质因子, 这一步是全部优化的来源。凡是 很大而"每个数的某个局部特征只取少数几种值"的题, 都值得先做这个转换。 - 埃氏筛的 DP 视角:
把"二次筛"变成了"筛掉的部分用上一阶段的值直接算",这就是 min_25 筛的核心, 也是它能把状态压缩到 个的原因。 - 溢出比超时更容易翻车:
时 已在 64 位边界, 只需 数组用 128 位、最终答案用 64 位输出即可,不必全盘 128 位。