说到AtCoder Beginner Contest 169这套题我个人印象最深的就是D题——Div Game。题目本身只有几十行没有花哨的数据结构也不涉及高级算法但它要求你在读完题之后立刻捕捉到一个关键的贪心结构一个数被拆成质因数之后每个质因数的指数部分实际上是一个独立的小游戏。想通这一层代码半小时内就能写完想不通的话很容易陷入手动模拟各种取法的泥潭。这篇文章我就从零开始完整复盘我对这道题的思考过程先是手算几个小数据找感觉再说明为什么质因数分解是必然选择然后给出可以直接提交的C和Python代码最后把我自己提交时踩过的几个坑列出来。整个思路不仅适用于这题也适用于以后遇到操作对象互不相同这一类限制条件的问题。1. 先从题意下手每次操作到底在干什么1.1 z的形态单个质数的正整数次幂题目给了一个正整数N要求我们反复对它做同一种操作选择一个正整数z使得当前N能被z整除然后把N变成N除以z。操作的限制是已经选过的z不能再选第二次。问最多能操作多少次。这里最关键的一个限定是z必须能被表示成p的e次方其中p是质数e是正整数。也就是说z只能是像2、3、4、5、7、8、9、11、13、16、25、27这样的数而不能是6、10、12、14、15、18这种由多个不同质数相乘得到的合数。有些读者第一次看的时候会把重心放在N要能被z整除上但真正的题眼其实是后半句已经选过的z不能再选。如果没有这个限制那对N2^3直接选2、再选2、再选2能操作三次加了限制之后指数相同的幂就只能用一次问题瞬间从无脑除法变成了合理分配指数。1.2 亲手算一个例子24怎么得到3次我先拿N24手算。24的质因数分解是2^3乘以3^1也就是24 2 × 2 × 2 × 3。现在枚举所有合法的z22^1、42^2、82^3、33^1一共四个候选。但最多能选几次先选z2N变成12再选z412除以4等于3最后选z3N变成1。一共3次。那能不能凑出4次此时2这个质因数的指数总共只有33这个质因数的指数只有1。z2、z4、z8三个候选里z8一旦选掉2的指数就清零了不可能再选其他带2的z而z2和z4虽然可以同时选但会消耗123个指数刚好用完。所以2这边最多贡献2次3这边最多贡献1次总次数就是3。这个例子里已经藏着全部答案的雏形每个质因数单独看能贡献的次数只和它的指数有关而且从小到大依次消耗指数是最优策略。1.3 顺序会影响结果但最优顺序是确定的一个小细节值得单独拿出来说操作顺序会影响最终次数吗会影响。还是拿24举例。如果我先选z8N变成3再选z3N变成1。一共只有2次。但如果按2、4、3的顺序选能达到3次。原因在于z8一次性把2的指数全部消耗完虽然留下了3这个质因数还能再操作一次但总共只用了两个z。更一般地说对同一个质因数p如果我们把它的指数a拆成若干个不同的正整数e1、e2、...、ek那么这k次操作分别选p^e1、p^e2、...、p^ek。要能顺利完成必须要e1 e2 ... ek ≤ a否则指数不够用。而想要次数k最大自然应该让这些e尽量小也就是取1、2、3、...、k。这就是这个题最核心的贪心思想。2. 关键一步从选数到分桶的转化2.1 为什么直接模拟必然超时如果不做任何数学转换最朴素的想法是枚举所有小于等于N的、形式为p^e的数然后用某种搜索策略尝试往N上套。但这样做有两个致命问题。第一候选z的数量太大。N跑到10^12量级时质数的数量是千万级别每个质数的幂又有一个到几十个不等整体枚举量根本无法接受。第二即使枚举出全部候选z怎么选才能让次数最多这看起来像一个组合优化问题暴力搜索的复杂度是指数级的完全不可行。所以走到这里就明白了必须从N的算术结构入手而不是从候选z入手。N只有唯一一种质因数分解方式这是解题的天然锚点。2.2 质因数分解后每个质因数成为独立子问题当N被写成p1^a1 × p2^a2 × ... × pm^am的形式时一次操作只能选择某个pi的幂次也就是说这次操作只会消耗p1、p2、...、pm中某一个质因数的指数其他质因数的指数完全不受影响。于是整个问题就分解成了m个互不干扰的小问题对于第i个质因数它的指数是ai我可以从它身上进行若干次操作每次取走一个互不相同的正整数指数取走的总指数不能超过ai。为什么说完全独立因为在操作层面我可以把所有针对p1的操作做完再做针对p2的操作再做p3的顺序任意互不影响。既然互不影响总答案就是每个质因数单独能贡献的最大次数之和。2.3 桶内问题的本质a个指数最多切几刀现在把问题抽象成这样一个模型我们手里有a个指数筹码每次操作必须要从这堆筹码里取走e个而且每次取的e都不能和之前取过的e重复问最多能取几次。比如a3时可取1和2共2次也可以取1和2和3不行12363。a5时可取1和2和...12365所以最多2次。a6时1236刚好3次。规律是如果想取k次这k次每次取的e互不相同那么这k个e的和最小就是12...k k(k1)/2。只要这个最小和不超过a我们就能按1、2、...、k的取法完成k次如果这个最小和已经超过a那任何k次取法都不可能成功。所以答案就是满足k(k1)/2 ≤ a的最大整数k。对每个质因数算出一个这样的k最后全部相加就是答案。3. 正解代码与复杂度3.1 质因数分解的写法与细节质因数分解的标准做法是从2开始枚举p只要p × p ≤ N就继续如果当前N能被p整除就把它除干净同时记录指数。这里有一个很多人第一次容易写错的细节循环条件是针对当前N的而不是一开始存的原始N。每次从N里除掉一个因子之后N会变小所以枚举范围也应该跟着变小。如果锁定成原始N代码依然正确但会多做一些无用功而如果写成for (long long p 2; p * p n; p)这种写法p*p会随着n的缩小而自然提前终止这正是我们想要的效果。3.2 每个桶的贡献计算对分解得到的每个指数cnt我可以在循环里累加int used 0; // 已经消耗的指数总数 int e 1; // 当前准备取走的指数 while (used e cnt) { used e; e; ans; }这段逻辑等价于从1开始依次尝试一直到再加下去就超界为止。也可以用二次方程直接算k_max floor((sqrt(8 * cnt 1) - 1) / 2)但写循环更贴近直觉而且cnt最多也就是60左右因为N最大10^122^40就超过10^12了循环次数极少完全不存在性能问题。3.3 C与Python参考实现C版本#include bits/stdc.h using namespace std; int main() { long long N; cin N; long long n N; int ans 0; for (long long p 2; p * p n; p) { if (n % p 0) { int cnt 0; while (n % p 0) { n / p; cnt; } int used 0; int e 1; while (used e cnt) { used e; e; ans; } } } if (n 1) { ans; } cout ans \n; return 0; }Python版本import math N int(input()) n N ans 0 p 2 while p * p n: if n % p 0: cnt 0 while n % p 0: n // p cnt 1 used 0 e 1 while used e cnt: used e e 1 ans 1 p 1 if n 1: ans 1 print(ans)最后那个if n 1的处理非常关键。循环结束后如果n不是1说明它剩下了一个大于sqrt(当前n)的质因数实际上因为n一直在变小这个剩余部分一定是一个质数它的指数是1所以它可以贡献一次操作因此ans直接加1。3.4 复杂度的一个严谨说法质因数分解部分的循环次数和p有关最坏情况是N是一个接近10^12的质数此时p要从2一路枚举到大约10^6也就是大约100万次判断每次判断都是O(1)的除法。这个量级在AtCoder常见的2秒时限内非常充裕。分解完成之后每个质因数对应的指数cnt做一次累加循环cnt的和最多约40因为2^40 1.0995×10^12 10^12所以这一部分复杂度可以忽略不计。整体复杂度就是O(sqrt(N))空间复杂度O(1)。4. 提交时的坑与验证清单4.1 循环边界与类型问题最容易出问题的就是类型。N最大值到10^12必须用64位整数C里就是long longint会直接溢出。另一个隐蔽的坑是循环条件p * p n。如果N特别大接近10^12时p最多到10^6pp是10^12量级long long完全放得下。但如果你以后做N到10^18的题pp会到10^18量级虽然long long也放得下但更稳妥的写法是p n / p避免任何乘法溢出的可能性。建议从一开始就养成写p n / p的习惯。还有一种错误是把循环写成for (int p 2; p * p n; p)p用了intp*p在p超过46340的时候就会溢出导致死循环或者错误结果。这个错误在本地测试小数据时完全看不出来一提交就挂。4.2 剩余大质数别漏掉质因数分解结束后如果n大于1说明最后剩下了一个大质数它的指数是1。很多人在这里会忘记处理导致答案少1。我比赛时第一次提交就因为这个WA了一次。当时N是一个大质数乘一个小因子分解完小因子后剩余的大质数没有计入答案。这个错误的麻烦在于它不影响N比较小的测试样例只有N本身带有大质数因子时才会暴露所以对拍小数据很难发现。因此我习惯在写完分解循环之后立刻写一行注释提醒自己剩余n1时指数为1贡献1次。4.3 一组可以直接对拍的测试数据我在本地验证时会准备一张表覆盖各种边界情况建议你也这么干N分解每个桶贡献答案1无无022^11133^11142^21次122162^1 × 3^111282^31232次2122^2 × 3^1112162^4123≤42次2242^3 × 3^1213362^2 × 3^2112642^612363次32^202^201234515≤205次5特别注意N4的情况。2的指数是2可选z有2和4。选2之后还能选4吗N变成24不能整除2不行。选4之后N变成1选不了2。所以最多1次而不是2次。这就是指数不够分配的直观表现。4.4 关于样例的手算直觉陷阱还有一个心理层面的坑。很多人第一次看到z不能重复会下意识认为候选z越多越好于是试图枚举所有p^e形式的数然后做某种最大匹配。其实一旦发现候选数规模爆炸就该退一步思考N的质因数分解。我的经验是遇到和整除、幂次、质数相关的操作题先花30秒把N分解了很多问题会瞬间清晰。这个思维习惯在做AtCoder数论题时非常有用。5. 赛后复盘这题的题眼与延伸5.1 互不相同约束的通用解法思路已经选过的z不能再选这个约束在这道题里等价于同一个质数p的指数e不能重复使用。而指数e是正整数想让总消耗最小且次数最多自然从1、2、3开始取。这个模式可以推广到很多问题只要有一个次数上限由若干个不同正整数的和决定答案往往就是解k(k1)/2 ≤ limit这个不等式。举一个同类例子假设你有a个相同的物品每次拿走不同数量的物品问最多能拿几次。答案和我上面推导的完全一样——对每个质因数我们本质上就是在做这件事。所以这道题虽然外表是数论题内里其实是标准的贪心。5.2 如果题目稍作变形把限制改成每次选的z必须互不相同且z可以是任意正整数不要求是质数的幂那答案会变成什么这时z只需要整除当前N并且互相不相同。由于N的质因数分解中任何一个由若干个质因数组合而成的约数都可以被选问题会变得完全不同复杂度也高得多。所以z p^e这个限制看似窄化了操作范围实际上恰恰是它让问题变成了可解的贪心。反过来如果把限制改成每次选的e必须严格递增结果也很简单从e1开始依次取1、2、3、...、a可以取a次。这时每个指数恰好能用一次答案就是指数本身。对比一下就能体会到互不相同比严格递增多了一个自由度但也正是因为取出的e可以是任意不同的正整数我们反而要用最小的1、2、3去填充计算方式就变了。5.3 这类题在比赛里的定位与应对节奏ABC的D题一般不会考特别冷门的算法而是考你能不能把一个看似搜索的问题简化成数学结构。这道题就是典型的例子代码不到30行难点全在思考过程。比赛时如果遇到这种题我的节奏是先手算N24、N36、N64这些小数据找规律一旦发现每个质因数独立立刻列式子验证确认贪心正确后直接写代码不再犹豫。整个过程控制在20分钟以内是比较理想的状态。如果手算小数据时发现答案和直觉对不上比如N12答案为什么不是3那就要回头重新审视指数消耗这个模型。这就是这道题检验能力的时刻——很多人在这里卡住是因为一直在枚举候选z而忘了从N的指数结构入手。最后分享一个我自己的小习惯写完这题之后我会把这套指数按1、2、3、...切分的贪心记录在错题本里标注为互不相同约束下的分配模型。后来做不少AtCoder的C/D题时这个模型反复出现每次都能节省不少思考时间。刷题的意义就在于此一道题带来的不是一题的正确而是一类问题的通用解法。