这题我印象挺深。当时刷洛谷的时候看到P2821“变幻数”第一反应是这不就是个循环相加嘛结果交上去被数据教做人。后来认真把数学模型捋了一遍才发现这题看着是模拟实际上考的是同余定理和数字根Digital Root那套东西。这篇文章就专门拆一拆这道题从最朴素的循环模拟开始一路讲到O(n)的直接公式解最后把提交评测时容易踩的坑也一并说了。如果你刚开始刷信奥的数论入门题或者对“数字根”这个概念还比较陌生这篇应该能省你不少时间。1. 题目到底在考什么先看清“变幻数”的数学本质1.1 变幻规则到底怎么定义先明确一下题目里这个变换规则对于给定的正整数如果它已经是个一位数那它本身就是变幻数如果不是就把它的每一位数字相加得到一个新数然后重复这个过程直到结果变成一位数为止。这个最终得到的一位数就是原数的变幻数。举个例子199 的变化过程是1 9 9 191 9 101 0 1所以 199 的变幻数是 1。再比如 123451 2 3 4 5 151 5 6变幻数就是 6。规则本身非常简单简单到很容易让人以为这是一道“送分模拟题”。但既然它能作为一个独立题目出现在题库里还专门起了个“变幻数”的名字事情就没这么简单。1.2 第一反应循环模拟的思路任何一个学过循环的选手看到这个题的第一反应大概率是这样while (数字不是一位数) { 把每一位相加; 更新数字; }这个思路完全正确暴力模拟一定能求出正确答案。真正的问题在于数字怎么存如果题目给的数据范围只是 int 甚至 long long 能装下的那这个题就真的是无脑模拟。但信奥题一般不这么善良P2821 的数据范围里输入可以是一个非常大的整数大到你没法用任何内置整数类型读进来。这就引出了第一个关键选择用 string 读入一位一位处理。1.3 出题人真正想让你发现的东西当输入数字的位数可能达到几千甚至几万位时表面上考的是“你会不会循环”实际上考的是“你能不能发现这个变幻过程背后的不变量”。这个不变量就是整个变换过程中数字对 9 取余的结果始终不变。也就是说不管你怎么把每一位加起来、再拆开、再加最终得到的一位数和最初的数在“模 9”的意义下是相等的。这个性质在数学上叫“数字根”Digital Root也叫数根。它有一个非常漂亮的结论一个非零正整数的数字根等于它对 9 取余的结果如果余数为 0则数字根为 9。换成公式就是digital_root(n) 1 (n - 1) % 9有了这个公式这题就从“反复循环模拟”变成了一次 O(n) 的数学计算读入字符串边读边对 9 取模最后按公式输出。这也是为什么我说这道题的本质是数论入门而不是模拟题。2. 为什么逐位相加会收敛数字根定理的完整推导2.1 从十进制展开看同余的本质要理解数字根必须回到十进制数的定义。任何一个整数 n 都可以写成n a_k * 10^k a_{k-1} * 10^(k-1) ... a_1 * 10 a_0其中 a_i 是每一位上的数字a_0 是个位a_1 是十位以此类推。现在关键的一步来了在模 9 的意义下10 和 1 是相等的因为 10 ≡ 1 (mod 9)。根据同余运算的乘法性质10 的任意次方也等于 1 的任意次方10^k ≡ 1^k ≡ 1 (mod 9)把这个结果代回十进制展开式n ≡ a_k a_{k-1} ... a_1 a_0 (mod 9)右边正好就是 n 的各位数字之和。这个结论非常关键一个数和它各位数字相加得到的和除以 9 的余数必然相同。变幻数每一次迭代都是“各位数字相加”所以每一次迭代都不会改变模 9 的余数。最终收敛到的那一位数当然也保持了这个余数。2.2 用“10 9 1”给新手一个直觉如果上面的同余推导对你来说还是有点抽象我们换一种更直白的拆法。还是以三位数 abc 为例它实际表示的是100a 10b c把 100 和 10 拆一下100a 10b c (99a a) (9b b) c (99a 9b) (a b c)其中 99a 9b 这一整块一定能被 9 整除剩下的 a b c 正好是各位数字之和。所以 n 除以 9 的余数就完全等于 a b c 除以 9 的余数。这个拆法可以推广到任意位数因为10^k 9 * 111...1 1中间那个 111...1 是 k 个 110^k 拆成“一堆 9 的倍数 1”之后所有“一堆 9 的倍数”都能被 9 整除最后剩下的就是各位数字之和。用一个生活化的类比模 9 余数就像你口袋里的硬币总价值把硬币从大票换成零钱、再换成更零的钱硬币的总价值不变。变幻数这个操作就是不断把钱换零最后换到只剩一枚硬币时它的面值当然还是原来的总价值在某种意义上的体现。2.3 最后一位数怎么定量确定连续变幻到最后我们得到一个一位数 d它只能在 0 到 9 之间。根据上面的推导d 必须满足d ≡ n (mod 9)对于正整数 nn 0最后得到的这个一位数不可能是 0因为一个正整数所有数位相加无论怎么加都不可能加到 0除非原数本身就是 0。所以最终 d 的取值范围实际上是 1 到 9。分两种情况如果 n mod 9 的结果在 1 到 8 之间那么 d 就等于 n mod 9。如果 n mod 9 的结果是 0说明 d 是 9 的倍数也就是说 d 9。写成常见的两种等价写法// 写法一三目判断 digital_root (n % 9 0) ? 9 : n % 9 // 写法二统一公式 digital_root 1 (n - 1) % 9这两个写法效果一样。写法一更好理解写法二更简洁但是要注意负数取模在不同语言里的行为差异后面我会专门说这个坑。2.4 一个必须单独处理的边界n 0题目一般说的是“正整数”所以 n 0 理论上不会出现。但有些改编题、多组数据题或者数据生成器不那么讲究会混进 0。如果 n 0按照定义0 已经是一位数它的变幻数就是 0。但如果用n % 9 0 ? 9 : n % 9这个写法0 % 9 0结果会错误地输出 9。如果用1 (n - 1) % 9这个写法在 C 里 (0 - 1) % 9 的结果是 -11 (-1) 0结果反而是对的只是这个“对”依赖 C 负数取模返回负数的特性比较脆弱。最稳妥的做法是读入之后先判断字符串是不是 0是就直接输出 0 结束。不要指望公式帮你兜底。3. C实现的关键细节与完整代码3.1 为什么必须用 string 读入而不是 long long如果题目没有明确说 n 的范围但又是这种“把每一位加起来”的题默认就要按大数处理。哪怕样例里给的是 199 这种小数字你也要有意识出题人给样例就是用来诱惑你写的 int 的。假设 n 有 10 万位long long 存不下直接读入就会出错或者数值被截断。而用 string 读入每一位只是一个字符字符串的长度理论上只受内存限制10 万位 20 万位都不是事。这是这类题的基本功看到“大整数”第一步永远是字符串。后面不论你是暴力模拟还是用数学公式读入这一步绝对不能省。3.2 暴力模拟版适合验证思路下面这份代码是完全按照题目描述的规则来的逻辑上最不容易出错适合用来做对拍验证。#include bits/stdc.h using namespace std; int main() { string s; cin s; while (s.length() 1) { int sum 0; for (char c : s) { sum c - 0; } s to_string(sum); } cout s endl; return 0; }注意几个细节cin s直接读入字符串不需要考虑前导零的问题。如果数据里有 000199 这种按字符串处理也不会影响最终结果因为每一位相加时前导零也只是加 0。c - 0是把字符数字转成整数。C 标准里字符 0 到 9 的 ASCII 码是连续的所以用这个表达式是安全且通用的。to_string(sum)是 C11 标准提供的函数把整数转成字符串。如果你的 OJ 用的编译器比较老可能需要自己写一个小函数转换。这个版本的复杂度我也说清楚。设初始字符串长度为 L第一次循环要遍历 L 位得到一个不超过 9L 的 sum。把这个 sum 转成字符串长度大约不超过 5 到 7 位因为 9L 即使 L 是 10 万sum 也才 90 万7 位。第二次循环遍历的就是这个短字符串后面几次循环位数更少。所以总的遍历量大约就是 L 常数依然是 O(L) 级别。也就是说暴力模拟其实在时间复杂度上是能通过的。那为什么还要学公式法因为公式法代码更短、思路更本质而且能帮你建立“同类题目直接秒杀”的敏感性。3.3 数学公式版边读边取模既然我们已经知道最终答案只和 n 对 9 取模的结果有关那就根本不用把整个大数完整保留下来只需要维护一个对 9 取模的变量边读字符边更新。#include bits/stdc.h using namespace std; int main() { string s; cin s; if (s 0) { cout 0 endl; return 0; } int mod9 0; for (char c : s) { int digit c - 0; mod9 (mod9 * 10 digit) % 9; } cout (mod9 0 ? 9 : mod9) endl; return 0; }这里有一个看起来不太起眼但很重要的操作mod9 (mod9 * 10 digit) % 9;这行代码做的事情是逐步还原“大数对 9 取模”的过程。我们读入字符串时是从高位往低位读的每读进一位之前的数就相当于整体乘了 10 再加上新的数字。这个变量 mod9 不需要真的存下完整的大数只在每一步对 9 取模即可因为(a * 10 b) % 9 ((a % 9) * 10 b) % 9这是同余运算的基本性质取模操作可以与加减乘交换顺序。所以边读边模最终得到的结果等同于把完整大数对 9 取模。举个例子输入 199初始 mod9 0读入 1mod9 (0 * 10 1) % 9 1读入 9mod9 (1 * 10 9) % 9 19 % 9 1读入 9mod9 (1 * 10 9) % 9 19 % 9 1最终 mod9 1199 % 9 1正确。然后因为 mod9 不等于 0直接输出 1。3.4 两版方案的对比下表可以很直观地看出两种解法的差异对比维度暴力模拟版数学公式版时间复杂度O(L)但常数略大O(L)常数极小空间占用需要字符串反复更新只需要一个 int 变量代码可读性直观符合题面描述需要理解同余原理边界处理天然兼容 n0需单独判断 n0思维价值验证模拟能力建立数论敏感度说实话在实际竞赛中两版代码都能 AC。我自己刚开始刷题时也是先写暴力的过了之后再看别人题解才意识到有公式解。这里并不是说暴力不好而是说如果你能多花几分钟想一想“这个变幻过程背后有没有不变量”这类题的收益会大很多。4. 提交评测时最容易踩的坑4.1 大数读入用错类型这是最常见、也最冤的错法。题目样例给你一个 199你顺手就int n; cin n;然后开始循环。本地跑样例全对一交上去大点直接 WA 或者 RE。因为真实数据里可能是一个几千位的数字int 和 long long 都装不下读进来的已经是截断或者错误的值后面算出来自然全错。解决办法就一句话这类题看到“每一位”三个字默认用 string 读入。哪怕题目数据范围第一眼看起来不是很大用字符串处理也不会有任何损失。4.2 字符转整数时用错方法新手经常写出这两种错误// 错误写法一直接类型转换得到的是 ASCII 码 int digit (int)c; // 错误写法二减成了 1 int digit c - 1;正确写法是c - 0。因为字符 0 的 ASCII 码是 48字符 9 的 ASCII 码是 57c - 0才能得到 0 到 9 的数字本身。这个坑在本地测试时不容易暴露因为如果你所有的c - 1错误一致地错一个可能结果碰巧对了一两个样例但数据一多就露馅。所以写的时候就要养成肌肉记忆字符数字转整数永远是c - 0。4.3 0 和 9 的边界混为一谈数学公式版里如果 n 是正整数且 n % 9 0答案是 9。但如果数据里混入了 0答案应该是 0 而不是 9。这是最容易翻车的一组边界值。我的建议是在代码最前面加一个特判if (s 0) { cout 0 endl; return 0; }不要试图用一个“看起来通用”的公式把所有情况都扛下来。公式是给人理解的代码是给机器跑的特判写清楚比什么都强。4.4 模拟版循环终止条件写错暴力模拟版里循环条件是while (s.length() 1)。这里有个隐含假设如果 s 已经是 0 或者 5 这种一位数循环体根本不会执行直接输出。这一点没问题。问题出在有些同学喜欢自己造轮子把终止条件写成while (sum ! 0)或者while (temp 9)这个时候如果 sum 变成了 0或者临时变量的类型不对就可能死循环或漏算。举例来说如果你把中间变量声明成 int而某次迭代中 sum 超过了 int 范围就会溢出变成负数循环条件判断就全乱了。虽然按 9 * 位数算不太可能超 int10 万位也就 90 万但如果题目数据位数再大你用 int 就可能出事。稳妥起见模拟版的中间变量直接用 long long。4.5 多组输入还是单组输入P2821 原题我记得是单组输入但不同 OJ 的拷贝版、改版题可能会改成分组输入也就是一直读到 EOF。如果你不确定可以写成string s; while (cin s) { // 处理 s }这个写法对单组输入同样适用输入一组输出一组不会出错。唯一的代价是代码稍微长了一行。在竞赛里能兼容多组输入的写法永远是更安全的选择。4.6 别忽略字符串中间的换行和空格如果是用cin s它默认会跳过空白字符所以换行空格都不是问题。但如果你图快用 scanf 或者手写快读就要注意字符串是不是被意外截断了。这类题最省心的就是用 C 的cin s如果担心输入量大加一行ios::sync_with_stdio(false); cin.tie(nullptr);就够了。5. 从变幻数延伸开数字根题型的通用套路5.1 快速识别“数字根”题型的三个特征刷题刷多了你会发现题目不会直接告诉你“这题考数字根”但以下几个信号出现两个以上你就要往模 9 的方向想变换操作是“把每一位相加”或者“反复求和直到一位数”。输入的数据范围极大明显不是内置整数类型能直接读入的。题目名称里带有“变幻”“数根”“数字和”“叠数”这类字眼。看到这些信号先别急着写 while 循环停下来想想每次变换前后什么量是不变的想清楚这个问题解题思路往往就出来了。5.2 如果变换规则变成了“每一位相乘”数字根之所以能用模 9 来算是因为“相加”这个操作和十进制展开在模 9 下同余。如果把规则改成“每一位相乘然后重复”情况就完全不同了一个数只要有一位是 0乘积直接变 0之后永远停在 0。如果所有位都是 1乘积永远是 1。其余情况乘积会迅速变小。这种题就不能直接套模 9 的公式了更多是考分类讨论和模拟退化的过程。所以学数字根的时候要理解它的成立条件不要背公式背成“所有变幻数都取模 9”。5.3 边读边取模一个能救命的通用技巧第 3 节代码里的mod9 (mod9 * 10 digit) % 9这个写法其实是一个更通用的技能用字符串表示的大整数想快速求它对某个数 m 的余数都可以用这个套路mod (mod * 10 digit) % m这里的 m 不限于 9只要是整数都成立。这个技巧在很多数论题里都会出现比如大数模 3、模 11、模 1e97 等。以后遇到“给你一个很长的数字字符串求它模 p 的余数”这种题这行代码可以直接抄。5.4 数字根在实际场景中的应用数字根不只是竞赛题现实世界也有它的影子。最常见的应用是校验码。比如信用卡卡号校验、ISBN 书号校验本质上都是用模运算来验证一串数字有没有抄错。虽然它们用的模数不一定是 9但核心思想是一致的给数据附加一个“变换后保持不变”的校验信息用它来检测错误。另外判断一个大整数能不能被 3 或 9 整除最快捷的方法也是看它各位数字之和能不能被 3 或 9 整除。这就是数字根公式在小学数学里的雏形各位数字之和能被 3 整除那这个数就能被 3 整除。原理和我上面推导的完全一致。5.5 学有余力可以做的延伸练习如果你把 P2821 搞明白了想趁热打铁巩固一下可以找这几类题目练手洛谷 P1012 拼数字符串和排序虽然不直接考模 9但考察大数的字符串处理快乐数各位数字平方和反复迭代理解“会收敛”和“会循环”的差异各位数字之和为特定值的构造题考察对十进制表示的逆向理解这些题都不是数字根的直接套用但做一遍能帮你把“十进制数与位数操作”这个概念盘活。说回 P2821 本身。我在实际提交的时候第一次确实用的是暴力模拟过了但心里总觉得这题不该这么简单。后来翻题解看到模 9 的公式再回头推导了一遍才真正理解“变幻”这个名字的深意——不管数字怎么变它对 9 的态度一直没变。最后分享一个小习惯遇到这类“反复迭代直到一位数”的题目先用 1 到 20 手算一遍找规律再决定是模拟还是套公式这个习惯帮我避过不少硬写循环的坑。