#3726. 数位和魔术

数位和魔术

题目描述

题目背景

魔术师小 K 正在表演他的拿手节目——数位和魔术。

题目描述

给定一个正整数 nn。小 K 每施展一次魔术,就会把当前的 nn 变为它的各位数字之和。

形式化地说,若 nn 的十进制表示从高位到低位依次为数字 d1,d2,…,dkd_1, d_2, \ldots, d_k,那么施展一次魔术后,nn 变为 d1+d2+⋯+dkd_1 + d_2 + \cdots + d_k。

例如:n=987n = 987,施展一次魔术后变为 9+8+7=249 + 8 + 7 = 24;再施展一次魔术后变为 2+4=62 + 4 = 6,此时 66 已经是一位数。

小 K 想知道:最少需要施展多少次魔术,才能使 nn 变成一个一位数(即 11 到 99 之间的整数)?请你求出这个最少次数,以及最终得到的那位一位数。

可以证明:按上述规则操作有限次后,nn 必定会变成一位数。

输入格式

一行,一个正整数 nn。

输出格式

一行,两个整数,以一个空格分隔:第一个整数是最少需要施展的魔术次数,第二个整数是最终得到的一位数。

样例

7
0 7 
987
2 6 

说明/提示

数据范围

  • 1≤n≤1091 \le n \le 10^9,使用 32 位整数(如 C++ 的 int)即可存储 nn。
  • 可以证明所需魔术次数不超过 33。

样例解释

  • 样例 1:77 本身就是一位数,不需要施展魔术,故输出 0 7。
  • 样例 2:第一次魔术把 987987 变为 9+8+7=249+8+7=24,第二次魔术把 2424 变为 2+4=62+4=6,66 是一位数,故输出 2 6。

解析

题解

题意分析

给定正整数 n,每次操作将 n 变为其十进制各位数字之和,求最少操作次数使 n 变为一位数(1 到 9),并输出该一位数。若 n 本身就是一位数,则次数为 0。

解题思路:直接模拟

本题最稳妥的做法就是严格按题意模拟:

  1. 若当前 n < 10,说明已经是一位数,停止操作;
  2. 否则计算 n 的各位数字之和 s,令 n = s,操作计数器加 1;
  3. 重复上述过程直到 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 · 入门 · 数学