贪心算法与最大真约数求解：从蓝桥杯ALGO-994题解到算法思维训练

1. 问题引入：从“最大分解”到“贪心”的直觉

最近在整理蓝桥杯的算法训练题时，又翻到了ALGO-994这道“最大分解”。题目本身描述很简单：给定一个正整数n，你需要对它进行一系列操作，每次操作是找到n的一个小于n的最大正约数（不包括n本身），然后用这个约数替换n，重复此过程直到n变为1。题目要求计算这个过程中所有“替换数”（即每次找到的那个最大约数）的和。

初看之下，很多人的第一反应可能是动态规划或者搜索，毕竟这看起来像一个状态转移问题。但稍微思考一下，或者动手模拟几个例子，比如n=10，过程是10 -> 5 -> 1，和是5+1=6；n=12，过程是12 -> 6 -> 3 -> 1，和是6+3+1=10。一个强烈的直觉就会浮现出来：每次都取当前数最大的真约数，似乎就能得到最终的最大和。这个直觉，其实就是贪心算法的核心思想。

为什么贪心会有效？我们可以这样理解：题目要求的是“替换数”的总和最大。在每一步，你用一个更小的数替换了当前的数。为了让后续步骤的“基数”尽可能大，从而可能产生更大的约数，你当然希望当前这一步替换掉的数尽可能小。但替换操作是固定的——用当前数的最大真约数替换它。所以，为了让“剩下的数”（即替换后的新数）在下一步有潜力找到更大的约数，我们需要这个新数本身尽可能大。而“当前数的最大真约数”正是所有可能的新数中最大的那个。因此，每一步都选择最大真约数，相当于每一步都为下一步创造了“最大可能”的起点，这是一种局部最优的选择。对于这个特定问题，可以证明（或者通过大量测试验证）这种局部最优的选择能导致全局最优解。

所以，这道题的本质，是考察对贪心策略的理解和实现，核心则在于如何高效地找到一个正整数的最大真约数。

2. 核心挑战：高效求解最大真约数

找到了贪心这个方向，接下来要解决的就是技术实现上的核心：对于一个给定的正整数current，如何快速找到它除了自身之外的最大正约数。

最直接的想法是暴力枚举。从current - 1开始向下循环，找到第一个能整除current的数。对于current最大为 10000 的数据范围（这是蓝桥杯算法训练题的典型范围），最坏情况下（比如current是一个质数），我们需要循环current-1次，而current在过程中会不断变小，但最坏的整体复杂度仍然接近 O(n²)，对于 10000 的规模勉强可以接受，但不够优雅，也容易在边界条件上出错（比如current=1时的处理）。

一个更高效、更标准的做法是利用因数成对出现的性质。对于任意一个正整数n，如果a是n的约数，那么n/a也必然是n的约数。并且，当a递增时，n/a递减。我们只需要从 2 开始遍历到sqrt(n)，找到的第一个能整除n的数i，那么n/i就是n的一个约数。由于i是从小到大找的，n/i就是从大到小出现的约数。我们要找的是最大的真约数，也就是除了n本身之外最大的那个数，它等于n / (n的最小真约数)。

因此，算法可以优化为：

1. 如果n == 1，它没有真约数，循环结束。
2. 从i = 2开始，遍历到sqrt(n)。
3. 如果n % i == 0，那么i就是n的最小真约数（1除外）。此时，n / i就是我们要找的最大真约数。
4. 如果循环结束都没找到这样的i，说明n是一个质数（除了1和自身没有其他约数）。那么它的最大真约数就是 1。

这个算法将寻找单个数的最大真约数的复杂度从 O(n) 降到了 O(√n)，对于本题的数据范围游刃有余，也是这类问题最标准的解法。

2.1 算法流程与代码实现（C语言）

理解了上述思路，我们可以用C语言清晰地实现出来。代码结构会非常直观。

#include <stdio.h> #include <math.h> // 函数：寻找n的最大真约数 int getMaxProperDivisor(int n) { // 如果n是1，没有真约数，按题目逻辑返回1（但实际调用时应先判断） if (n <= 1) return 1; int limit = (int)sqrt(n); for (int i = 2; i <= limit; i++) { if (n % i == 0) { // i是n的最小真约数，n/i就是最大真约数 return n / i; } } // 循环结束没找到，说明n是质数，最大真约数是1 return 1; } int main() { int n; scanf("%d", &n); long long total_sum = 0; // 使用long long防止累加和溢出 int current = n; // 当current大于1时，持续进行分解操作 while (current > 1) { int next = getMaxProperDivisor(current); // 找到当前数的最大真约数 total_sum += next; // 将替换数加入总和 current = next; // 用找到的约数替换当前数 } printf("%lld\n", total_sum); return 0; }

这段代码中，getMaxProperDivisor函数封装了寻找最大真约数的逻辑。主循环while (current > 1)模拟了题目描述的分解过程，直到数变为1为止。使用long long类型存储总和total_sum是一个好习惯，因为即使n=10000，不断累加的结果也可能超出int范围。

2.2 一个具体的计算示例

让我们以 n=24 为例，手动走一遍流程，验证代码逻辑：

1. current = 24。sqrt(24)≈4，从2开始遍历，24 % 2 == 0，所以最大真约数是24 / 2 = 12。total_sum = 0 + 12 = 12。current更新为 12。
2. current = 12。sqrt(12)≈3，从2开始，12 % 2 == 0，最大真约数是12 / 2 = 6。total_sum = 12 + 6 = 18。current更新为 6。
3. current = 6。sqrt(6)≈2，从2开始，6 % 2 == 0，最大真约数是6 / 2 = 3。total_sum = 18 + 3 = 21。current更新为 3。
4. current = 3。sqrt(3)≈1，循环i=2不满足i<=1，直接跳过。因此3是质数，最大真约数是 1。total_sum = 21 + 1 = 22。current更新为 1。
5. current = 1，循环结束。最终总和为 22。

过程为：24 -> 12 -> 6 -> 3 -> 1，和为 12+6+3+1 = 22。

3. 贪心策略的正确性分析与边界讨论

虽然我们的直觉和大量测试都支持贪心策略，但在算法题中，尤其是训练阶段，思考一下“为什么这样做是对的”很有必要。这不仅能加深理解，也能在面对类似新问题时，判断贪心是否适用。

对于本题，我们可以尝试进行不严谨但有助于理解的论证：

• 目标：最大化序列a1, a2, ..., ak的和，其中a1是n的最大真约数，a2是a1的最大真约数，依此类推，直到ak = 1。
• 贪心选择：在每一步，我们都选择当前数x的最大真约数作为a_i。
• 最优子结构：假设从x开始的最优解得到的和是S(x)。如果我们第一步选择了最大真约数d，那么剩下的问题就是从d开始分解。如果S(d)是从d开始能得到的最优和，那么从x开始的总和就是d + S(d)。贪心策略断言d（最大真约数）的选择能使得d + S(d)最大。
• 为什么选最大的d可能更好？因为d直接贡献于总和，并且d越大，下一步的起点就越高。一个更大的起点d，其自身的最大真约数也可能更大（尽管不是绝对，例如质数的情况）。反之，如果选择一个更小的真约数d'，那么d'对总和的直接贡献更小，并且给下一步留下了一个更小的数，其后续能产生的约数总和S(d')很可能也不如S(d)大。因此，没有理由去选择一个更小的d'。

当然，严格的数学证明可能需要更复杂的归纳或反证。但在算法竞赛和训练中，对于数据范围有限且题意清晰的题目，通过逻辑推理和样例验证贪心策略的可行性是常用且有效的方法。

注意：这里有一个非常关键的边界情况，就是n=1的时候。根据题目描述，操作直到n变为 1 停止。那么初始值n=1呢？此时，没有任何操作可以执行，替换数的和应该是 0。我们的代码中，主循环条件是while (current > 1)，如果输入n=1，current初始就是 1，循环不会进入，total_sum保持为 0，输出 0，这是正确的。在getMaxProperDivisor函数中，我们对n<=1的情况返回了 1，这只是函数的一个保护性设计，因为在主循环中，我们保证不会用1去调用这个函数（因为current=1时循环已结束）。但在其他上下文调用此函数时，这个保护就有用了。

4. 从解题到举一反三：算法思维的延伸

解决了ALGO-994，我们不能仅仅停留在AC（Accept，通过）的喜悦上。这道题像一把钥匙，可以打开几扇通往其他重要算法概念的大门。

4.1 与“质因数分解”和“最小质因数”的关联

我们寻找最大真约数的函数，其核心是找到n的最小质因数（当然，如果n是质数则返回n本身）。因为n除以这个最小的质因数，就得到了n的最大真约数（该约数包含了n的其他所有质因数）。

这直接引出了质因数分解的经典算法。标准的试除法分解质因数，就是从i=2开始，当n % i == 0时，就记录i是一个质因数，然后将n除以i，直到n % i != 0再增加i。这个过程和我们找最小质因数的循环如出一辙。因此，本题的解法可以看作是对质因数分解知识的一次轻度应用。

// 一个简单的质因数分解示例 void primeFactorization(int n) { printf("%d = ", n); for (int i = 2; i * i <= n; i++) { while (n % i == 0) { printf("%d ", i); n /= i; } } if (n > 1) { printf("%d", n); // 处理最后剩下的那个质数 } printf("\n"); }

对比一下，getMaxProperDivisor函数在找到第一个质因数i后，直接返回n / i就结束了。而质因数分解则要一直除下去，直到n被彻底分解为质数的乘积。理解了这个联系，以后再遇到需要找最小质因数或者需要快速判断一个数是否为质数（即循环完都找不到约数）的题目，你就能立刻联想到类似的循环结构。

4.2 性能优化：预处理与记忆化

本题的数据范围（n <= 10000）很小，O(n√n) 的算法完全足够。但如果数据范围扩大到 10^6 甚至 10^7，我们每次循环都从2开始找约数，整体复杂度可能会成为瓶颈。

这时可以考虑预处理。我们可以用埃拉托斯特尼筛法（埃氏筛）或其变体，预先计算出每个数的最小质因数。这样，对于任意一个数n，我们可以在 O(1) 时间内知道它的最小质因数spf[n]，那么它的最大真约数就是n / spf[n]（当n是质数时，spf[n] = n，此时最大真约数为1）。

#define MAX_N 1000000 int spf[MAX_N + 1]; // spf[i] 存储 i 的最小质因数 void sieve() { for (int i = 0; i <= MAX_N; i++) spf[i] = i; // 初始化 for (int i = 2; i * i <= MAX_N; i++) { if (spf[i] == i) { // i是质数 for (int j = i * i; j <= MAX_N; j += i) { if (spf[j] == j) { // 如果j还没被标记过 spf[j] = i; // i是j的最小质因数 } } } } } int getMaxProperDivisorFast(int n) { if (n <= 1) return 1; if (spf[n] == n) return 1; // n是质数 return n / spf[n]; }

通过预处理，我们将每次查询的复杂度从 O(√n) 降到了 O(1)，代价是 O(n log log n) 的预处理时间和 O(n) 的空间。这在处理大量查询时非常高效。这种“空间换时间”和“预处理”的思想，在算法竞赛中至关重要。

4.3 错误思路辨析：为什么不是动态规划？

看到“最大”、“分解”、“过程”这些词，有些同学可能会想用动态规划（DP）。设dp[i]表示数字i经过题目操作能得到的最大和。那么状态转移方程似乎是：dp[i] = max(dp[j] + j) for all j that is a proper divisor of i？ 或者dp[i] = i + max(dp[j])？

仔细分析就会发现不对。题目中的操作是确定的：你必须用当前数的最大真约数替换它，而不是任意选一个约数。因此，从i出发，下一步的状态是唯一确定的（即getMaxProperDivisor(i)），不存在一个“最大”的选择。所以，这根本不是一个求最优决策的问题，而是一个模拟确定过程的问题。贪心在这里不是一种“策略选择”，而是对题目给定操作规则的直接执行。

这是一个很好的教训：不要被题目中的“最大”二字迷惑，一定要仔细理解操作过程的定义。这里的“最大”指的是最终求和的结果最大，而这个结果是唯一确定的，由初始的n和固定的操作规则决定，不需要我们通过比较不同决策来求极值。

5. 实战测试与常见“坑点”

理论清晰了，代码写好了，最后一步就是在各种情况下测试我们的程序，确保其健壮性。以下是一些关键的测试点和常见错误：

1. 最小输入n=1：应输出0。确保循环条件正确，不会进入死循环或调用非法函数。
2. 质数输入：如n=17。过程应为17 -> 1，和为1。检查你的getMaxProperDivisor函数对于质数是否返回1。
3. 完全平方数：如n=36。sqrt(36)=6，最大真约数是36/2=18？等等，这里有个细节。循环从i=2开始，36%2==0，所以返回36/2=18，正确。但要注意，36的约数包括6，而6*6=36。我们的循环条件i <= sqrt(n)是包含等号的，这对于完全平方数正确处理其平方根因子是必要的。如果条件是i < sqrt(n)，对于n=4，sqrt(4)=2，循环i=2可能不会被判断（取决于浮点数精度和整数转换），导致错误地将4判为质数。
4. 较大的非质数：如n=9999。可以手算验证，9999 = 3 * 3333，所以第一步最大约数是3333。3333 = 3 * 1111，第二步是1111。1111 = 11 * 101，101是质数，所以第三步是101，第四步是1。和为3333+1111+101+1=4546。用程序跑一下看结果是否一致。
5. 累加和溢出：虽然本题n<=10000，和不会太大，但养成使用long long的习惯很重要。如果n更大，比如n=10^6，过程中产生的数加起来很可能超过int范围（约21亿）。在C语言中，int通常是32位，最大值约21.47亿。用long long（通常是64位）可以避免这个问题。

一个编码细节：在getMaxProperDivisor函数中，sqrt函数返回double，我们将其赋值给int会进行截断。循环条件i <= limit是安全的。另一种更严谨、完全避免浮点数运算的写法是for (int i = 2; i * i <= n; i++)。这样用乘法判断，避免了浮点数精度和类型转换的潜在问题，是更推荐的做法。

int getMaxProperDivisor(int n) { if (n <= 1) return 1; for (int i = 2; i * i <= n; i++) { // 使用 i*i <= n 代替 sqrt if (n % i == 0) { return n / i; } } return 1; // n是质数 }

最后，将所有这些点串联起来，我们不仅解开了ALGO-994“最大分解”这道题，更完成了一次小型的算法思维训练：从理解题意、形成贪心直觉，到设计高效的核心函数，再到分析正确性、关联其他知识、考虑优化和边界情况。这个过程，远比单纯记住这道题的答案重要得多。在算法学习的道路上，这种拆解和联想的能力，会让你在面对新的、看似复杂的题目时，能够更快地找到突破口。