#3726. 数位和魔术
数位和魔术
题目描述
题目背景
魔术师小 K 正在表演他的拿手节目——数位和魔术。
题目描述
给定一个正整数 。小 K 每施展一次魔术,就会把当前的 变为它的各位数字之和。
形式化地说,若 的十进制表示从高位到低位依次为数字 ,那么施展一次魔术后, 变为 。
例如:,施展一次魔术后变为 ;再施展一次魔术后变为 ,此时 已经是一位数。
小 K 想知道:最少需要施展多少次魔术,才能使 变成一个一位数(即 到 之间的整数)?请你求出这个最少次数,以及最终得到的那位一位数。
可以证明:按上述规则操作有限次后, 必定会变成一位数。
输入格式
一行,一个正整数 。
输出格式
一行,两个整数,以一个空格分隔:第一个整数是最少需要施展的魔术次数,第二个整数是最终得到的一位数。
样例
7
0 7
987
2 6
说明/提示
数据范围
- ,使用 32 位整数(如 C++ 的
int)即可存储 。 - 可以证明所需魔术次数不超过 。
样例解释
- 样例 1: 本身就是一位数,不需要施展魔术,故输出
0 7。 - 样例 2:第一次魔术把 变为 ,第二次魔术把 变为 , 是一位数,故输出
2 6。
解析
题解
题意分析
给定正整数 n,每次操作将 n 变为其十进制各位数字之和,求最少操作次数使 n 变为一位数(1 到 9),并输出该一位数。若 n 本身就是一位数,则次数为 0。
解题思路:直接模拟
本题最稳妥的做法就是严格按题意模拟:
- 若当前 n < 10,说明已经是一位数,停止操作;
- 否则计算 n 的各位数字之和 s,令 n = s,操作计数器加 1;
- 重复上述过程直到 n < 10,最后输出计数器与当前的 n。
操作次数为何很少? 由于 n ≤ 10^9,n 至多 10 位,一次操作后的数位和最大不超过 81(例如 999999999 的数位和为 81),而 81 再操作一次得到 9。因此对题目数据范围,最多约 2~3 次操作后必然变为一位数,这与题面提示一致。
为什么不用数位根公式? 数学上,最终的一位数即 n 的数位根(digital root),对 n > 0 有数位根 = 1 + (n-1) mod 9;操作次数也可按 n 是否为一位数、是否为 9 的倍数等情况分段讨论得到。但公式法需要额外处理诸多边界(如 n 本身是一位数时次数为 0,而非公式直接结果),容易写错。模拟法逻辑与题面描述一一对应,天然涵盖所有边界情况,代码短、正确性显然,是本题的最佳选择。
复杂度分析
- 时间复杂度:每次数位和计算需要 O(log₁₀ n) 次除法与取模;操作总次数不超过 3 次,故总时间复杂度为 O(log n),对 n ≤ 10^9 而言只有几十次基本运算,远低于 1 秒时限。
- 空间复杂度:O(1),只使用常数个变量。使用
long long(或题面所述的 32 位int)即可安全存储 n 及中间结果(数位和最大 81)。
样例验证
- n = 7:已是一位数,不操作,输出
0 7; - n = 987:第一次操作 987 → 9+8+7 = 24,第二次操作 24 → 2+4 = 6,共 2 次,最终一位数为 6,输出
2 6。
两个样例均与期望输出一致,算法正确。
来源
AI 生成 · 系统大模型(域):GLM-5.3-Flash · 入门 · 数学