企业官网建设流程全解析

开门见山。ABC169的D题，Div Game，题目描述很短，但里面藏了一个很容易让新手翻车的限制条件。我打这场模拟的时候，第一版代码写完样例全过，交上去WA了一大片，回头逐字读题才发现自己漏掉了“选择的整数不能重复”这个关键设定。这篇文章就把这道题从题意拆解、数学推导到代码实现完整过一遍，顺便把我在这个题上踩过的坑都摆出来，给准备打ABC或者刚刚开始刷数论题的同学做个参考。不管你是刚接触质因数分解，还是想看看这类“看似模拟、实为数学”的题怎么分析，这篇内容都能帮上忙。

1. 题目到底在问什么：拆解题意与关键陷阱

1.1 原题大意与操作规则

题目给了你一个不太大的正整数 N，范围是 1 到 10^12。你要执行若干次操作，每次操作需要选择一个整数 x，这个 x 必须满足三个条件：

• x 大于 1；
• x 必须是当前 N 的约数，也就是 N 能被 x 整除；
• x 必须可以写成 p^e 的形式，其中 p 是质数，e 是正整数。

操作完成后，把当前的 N 替换成 N/x。重复这个过程，直到没法再选为止，问最多能操作多少次。

举个最直白的例子，N = 24。你可以先选 x = 2，24 变成 12；再选 x = 4，12 变成 3；最后选 x = 3，3 变成 1。总共三次，这就是答案。看起来就是一个不断“分解出质数幂因子”的模拟过程，没什么特别的。

但问题在于，为什么不能一直选 x = 2 呢？24 能被 2 整除，12 也能被 2 整除，6 也能被 2 整除，如果允许反复用同一个 2，那对 N = 2^30 这种数不就能操作 30 次了？真实答案并不是这样，因为原题里还有一个容易看漏的限制，我们下一节讲。

1.2 最容易忽略的隐藏条件：操作对象不可重复

原题在描述操作规则时，明确表示你不能选择之前已经使用过的同一个 x。这个条件看起来不起眼，但它是整个题目的核心，直接决定了正确做法从“模拟除法”变成了“数学分组”。

这样说可能还不太直观，我们对比一下两种设定下的结果。假设 N = 8 = 2^3。如果允许重复使用 x = 2，那么你可以连续操作三次，8 → 4 → 2 → 1。但在真实题目中，第一次选了 x = 2 之后，第二次就不能再选 2 了，你只能选 4 或者 8。如果第二次选 4，那么 8 先变成 4，再变成 1，总共两次。如果第一次就选 8，那一次就结束了。所以正确答案是 2，而不是 3。

这个限制带来的一个重要推论是：对于同一个质因子 p，你每次消耗它的数量必须互不相同。你有 e 个 p 的幂次要消耗，每次消耗的量是一个正整数，而这些正整数不能重复。为了让操作次数尽量多，你自然希望每次消耗得尽量少，也就是 1、2、3……这样一路加下去。

1.3 一个手算例子：从 24 出发理解整个过程

还是拿 N = 24 来演算，N = 2^3 × 3^1。先看质因子 2，指数是 3。由于操作数不能重复，这个质因子能支撑的最多操作次数，就是最大的 t，使得 1 + 2 + ... + t ≤ 3。1 + 2 = 3，刚好满足，所以 t = 2。也就是说，针对 2 这个质因子，最优做法是第一次消耗 1 个 2（选 x = 2），第二次消耗 2 个 2（选 x = 4），刚好把 2^3 全部用完。

再看质因子 3，指数是 1。1 已经是最大的满足 1 + 2 + ... + t ≤ 1 的 t 了，所以 t = 1，也就是只能选一次 x = 3。两部分相加，24 的答案就是 2 + 1 = 3。

这个手算过程其实就是完整算法的雏形：先质因数分解，再对每个指数求它能拆成多少个不同的正整数之和，累加起来。下一节我们详细说为什么这个思路是对的，以及另外两个常见错误解法错在哪里。

2. 从暴力到正解：为什么不能直接“能除就除”

2.1 错误解法一：每次选最小的质因子

很多人看到这个题的第一反应是贪心，既然要操作次数最多，那我就每次选最小的合法 x，比如 x = 2 或者 x = 3。这个思路在不限制重复选择的题目里是对的，但在这个题里，一旦一个 x 被用过，后面就不能再用了。

还拿 N = 8 举例。如果按“每次选最小”来贪心，第一次选 x = 2，N 变成 4；第二次想再选 x = 2，但题目不允许，只能选 x = 4，N 变成 1。操作次数是 2，看起来好像也能得到正确答案，但这只是巧合。换一个数据，N = 2^4 = 16，每次选最小会变成：选 2 → 8，此时 2 不能再选，只能选 4 → 2，此时 4 也用过了，还能选 2 吗？不能，只能选 16？但 16 不是当前 N = 2 的约数，所以操作结束，总共 2 次。但真实最优是选 2 → 8，选 4 → 2，选 2？不对，2 已经在第一步用过了，所以也不行。仔细演算发现 16 = 2^4，满足 1 + 2 + ... + t ≤ 4 的最大 t 是 2（因为 2^4：1 + 2 = 3 ≤ 4；再加 3 的话 6 > 4），所以答案是 2，刚好和贪心一致。再试 N = 2^5 = 32：1 + 2 + 3 = 6 > 5，所以最大 t = 2？不对，1 + 2 = 3 ≤ 5，再加 3 是 6 > 5，所以 t = 2？但 1 + 2 + 3 = 6 不行，所以答案是 2？等一下，N = 32 = 2^5，最大 t = 2，答案 2。可是贪心“每次选最小”会：先选 2 → 16，再选 4 → 4，然后 2 不能重复选，4 也不能，选 8？当前 N=4，8 不是约数，结束，恰好 2 次。两者一致。

看起来贪心有时候也能撞对，但这不是因为它找到了最优策略，而是数据小的时候碰巧等价。换一个组合数较多的场景，比如 N = 2^3 × 3^3。正确算法：2^3 贡献 2，3^3 贡献 2，总和 4。贪心“每次选最小的 x”：从小到大找，x = 2 合法，N 变成 2^2 × 3^3；下一个最小合法 x 是多少？x = 2 已经用过，不能用；x = 3 最小？但当前 N = 2^2 × 3^3，x = 3 是合法的，消耗 1 个 3，N 变成 2^2 × 3^2；下一步最小合法 x 是 4（2^2），N 变成 3^2；下一步 x = 9（3^2），N 变成 1。总次数 4。这次碰巧一样，但过程完全不同。真正的反例需要指数更大，比如 N = 2^5。正确 t = 2，而贪心“每次选最小”第一次选 2，第二次选 4，之后没法操作，也是 2。所以“每次选最小”整体表现经常和正确答案相等，但它依赖的是每次确实只消耗 1、2、3……这个序列，本质上是三角数策略的模拟，只是通过遍历来实现，而不是因为它理解了不可重复的限制。

2.2 错误解法二：每次选最大的幂次

另一个常见的错误是反过来，觉得既然 x 不能重复，那我每次选尽可能大的 p^e，一步到位。这个想法错得更明显。以 N = 64 = 2^6 为例，如果第一次选最大的合法 x = 64，那么一次就把 N 变成 1，答案 1。但真实答案是 3：选 x = 2 → 32，选 x = 4 → 8，选 x = 8 → 1。因为指数 6 可以拆成 1 + 2 + 3，所以能操作三次。

这个反例非常清晰地说明了“每次消耗得越少越好”的直觉：你每次选的 x 不能相同，因此要尽量把消耗量控制在最小的不重复正整数序列上。选一个大数，相当于把后续很多操作机会一次性浪费掉了。

2.3 正解思路：质因数分解后逐项累加

现在我们正式推导正解。

把 N 分解成质因数的乘积：

N = p1^e1 × p2^e2 × ... × pk^ek

由于 x 只能写成单个质数的幂，任何一次操作消耗的只能是某个 p_i 的一部分指数，不可能同时消耗两个不同质因子。因此，整个操作过程可以被拆分成若干组，每组只针对一个质因子进行，不同质因子之间的操作互不影响。

只看其中一个质因子 p，它的指数是 e。每次操作会消耗这个质因子的 b 个幂次，b 是一个正整数，而且所有操作中同一个 b 不能出现两次，否则对应的 x = p^b 就重复了。另外，所有 b 加起来必须等于 e，因为最终要把这个质因子的指数全部用完。

问题变成了：有 e 个“库存”，每次要拿一个不重复的正整数 b，拿走的数量之和正好等于 e，问最多能拿几次。为了让次数最多，肯定优先拿最小的正整数：1、2、3……因为这些数最小，单位“库存”能换来的操作次数最多。假设最多能拿 t 次，那么这些数至少是 1、2、...、t，它们之和为 t(t+1)/2。因此条件就是：

t(t+1)/2 ≤ e

最大的 t 就是答案中该质因子贡献的部分。这个 t 在数学上可以通解，直接解一元二次不等式：

t² + t - 2e ≤ 0

所以 t = floor((sqrt(8e + 1) - 1) / 2)。当然，因为这里的 e 最大也就 39 左右，直接循环累加也能搞定，后面代码部分我会给出三种写法。

把所有质因子的 t 累加起来，就是最终答案。复杂度主要在质因数分解上，O(sqrt(N))，对于 10^12 的 N 来说完全没问题。

3. 完整实现与细节优化

3.1 C++ 代码及逐行说明

下面是这道题的 C++ 实现，也是我比赛时最终使用的版本。代码不长，但每一行都有讲究。

#include <bits/stdc++.h> using namespace std; int main() { long long N; cin >> N; long long ans = 0; for (long long i = 2; i <= N / i; i++) { if (N % i == 0) { long long e = 0; while (N % i == 0) { N /= i; e++; } // 求最大的 t 满足 t * (t + 1) / 2 <= e long long t = 0; while ((t + 1) * (t + 2) / 2 <= e) { t++; } ans += t; } } if (N > 1) { ans += 1; } cout << ans << endl; return 0; }

几个关键点说一下。循环条件我写的是i <= N / i，等价于i * i <= N，但避免了乘法溢出。虽然这道题的 N 只有 10^12，i * i最多 10^12，不会真的溢出 long long，但这是一个很好的编码习惯，尤其在题目改大到 10^18 的时候能帮你躲过一个大坑。

while ((t + 1) * (t + 2) / 2 <= e)这句是在找满足条件的最大 t。因为 e 很小，从 0 开始往上试就足够了。当然这里有更直接的做法，我后面单独说。

最后if (N > 1) ans += 1;处理的是分解完剩下的质因子。比如 N = 17，循环从 i = 2 开始，17 不能被任何小于等于 sqrt(17) 的数整除，循环结束，N 仍然等于 17，它是一个指数为 1 的大质因子，只能操作一次，所以答案加 1。这个分支忘了写，是很多初学者丢分的地方。

3.2 Python 实现与循环条件陷阱

Python 版本思路完全相同，但有一个地方和 C++ 不太一样，就是循环条件的写法。

import math def solve(): N = int(input()) ans = 0 i = 2 while i * i <= N: if N % i == 0: e = 0 while N % i == 0: N //= i e += 1 t = 0 while (t + 1) * (t + 2) // 2 <= e: t += 1 ans += t i += 1 if N > 1: ans += 1 print(ans) if __name__ == "__main__": solve()

Python 里i * i <= N没有溢出问题，但有一个效率隐患：如果 N 是一个很大的质数，比如 999999999989，这个循环要一直跑到大约 10^6 才会停止，在 Python 里也就是一秒左右，能接受。不过要注意，循环里的i += 1必须放在if N % i == 0外面，否则当 N 被除成 1 之后，i 不会再增长，会陷入死循环。这个细节我身边真有人踩过。

3.3 求三角数 t 的三种写法

针对每个指数 e，求最大 t 让 t(t+1)/2 ≤ e，实现方式有很多。除了上面代码里的循环累加，我再给你两种，可以根据习惯选用。

第一种，直接解一元二次方程。利用求根公式：

long long t = (sqrt(8.0 * e + 1.0) - 1.0) / 2.0;

用浮点开根，然后向下取整。注意sqrt的结果在 e 特别大的时候可能有浮点误差，但 e 最大也就 39，完全用不着担心。如果题目把 N 的范围扩大到 10^18，e 最大也就 60，依然安全。

第二种，用二分。虽然有点小题大做，但作为通用写法也可以：

long long l = 0, r = e; while (l < r) { long long mid = (l + r + 1) / 2; if (mid * (mid + 1) / 2 <= e) { l = mid; } else { r = mid - 1; } } ans += l;

第三种，就是我上面代码里的递增试探。因为 e 非常小，t 最多也不会超过 9（不信你算算 9×10/2 = 45，已经超过 39 了），所以这个写法其实是最快的，也最容易理解。我最后交上去的就是这个版本，稳得很。

4. 踩坑实录与变式扩展

4.1 我实战中遇到的三个典型错误

这个题我实际提交过程中，前两次都 WA 了。第一次是因为没理解“不能重复选择同一个 x”，直接把每个质因子的指数 e 加到答案里去了。比如 N = 64，我的代码输出 6，正确答案是 3。那次 WA 给我留下的印象非常深，从此之后我养成了一个习惯：凡是涉及“选择规则”的模拟题，先把规则里所有的“不能”“禁止”圈出来，再看看它会不会影响贪心策略。

第二次错在质因数分解的细节。当时我用 int 存循环变量 i，然后在循环条件里写i * i <= n。N 是 long long，i 是 int，i 增长到 100000 的时候 i*i 是 10^10，超过了 int 的最大值，溢出成负数，导致循环条件永远成立，程序直接超时。从那以后我写循环条件统一用i <= n / i，省心很多。

第三次是忘记处理剩下的质因子。N = 17 这种输入，分解循环跑完，N 还是 17，如果不加最后的if (N > 1)，答案就是 0，显然不对。这个属于典型的遗漏边界，不是思路问题，但很致命。

4.2 问题速查表

把常见错误和对应修正整理成一个表格，方便你比赛前快速自查。

4.3 如果题目换个问法：思路迁移与扩展

Div Game 这个题的核心数学结构是“把指数 e 分割成尽可能多互不相同的正整数”，这个结构在很多题目里都会出现，只是换了一层皮。

比如题目改成：给定 N，每次选择一个正整数 x，要求 x 是 N 的约数且 x 是某个质数的幂，允许选择重复的 x，那答案就简单多了，直接对每个指数 e 累加 e，因为每次选 x = p 可以把指数消耗 1，重复 e 次。这个反向变式可以帮你把原题的限制条件看得更清楚：不可重复才是难点来源。

再比如，把最终目标从“让 N 变成 1”改成“让 N 变成某个给定的 M”，那就要稍微调整一下思路。由于每次只能消耗单个质因子的指数，N 和 M 的质因数分解如果存在不一致的质因子，或者某个质因子的指数比 M 小，那就直接无解。可操作的空间是每个质因子剩余的那部分指数，仍然可以用三角数来算。

还有一个相关方向是约数个数。质因数分解后，N 的约数个数等于 (e1+1)(e2+1)...(ek+1)，这是 ABC 很多数论题的基础。Div Game 本质上是在问“沿着一棵约数链往下走，前一步的约数不能重复，最多走多远”，虽然它的约数形式被限制成了质数幂，但思考路径和约数类题目很一致。做这一类题，先把质因数分解练熟，后面遇到约数和、欧拉函数、乘法逆元，都会轻松很多。

最后留一个小建议。遇到这种“规则简单但限制微妙”的题，别急着写代码，先手算两三个小数据，把最优操作路径完整写出来。比如 N=16、N=32、N=64 各写一遍，你会很快发现 1+2+3 的规律，后面就不容易跑偏了。我在这个题上吃过亏之后，每次打 ABC 都会刻意用这种方式验证一下贪心直觉，实测下来对正确率的提升非常明显。