BISHI60　大水题¶

简单通过率 81.18%python3样例通过牛客 AC

讲解章节：数论基础

一句话

反复数位求和直到只剩一位，输出这一位（数字根）。

解题思路¶

这题考什么¶

数字根（digital root）的闭式公式。十进制下 10 ≡ 1 (mod 9)，所以「一个数」与「它的数位和」模 9 同余。反复求数位和不改变模 9 的值，最终稳定在一个 1..9 的个位数上，于是

dr(n) = 1 + (n - 1) mod 9      (n >= 1)

（用 n % 9 会把 9、18、27 算成 0，必须用这个偏移写法。）

为什么一定会停：一个 d 位数的数位和不超过 9d，而 d >= 2 时 9d < 10^(d-1)，位数严格减少，所以反复求和必然掉到一位数并停住。停住时它是 1..9 中与 n 同余（模 9）的那一个 —— 这就唯一确定了答案。

数据规模与复杂度¶

n <= 1e9，一组数据，O(1)：一次取模、一次加法，与 n 的位数都无关。模拟数位求和也只有两三轮（1e9 的数位和最大 81，再一轮就到个位），但公式版更能说明「为什么是 9」，而且对任意大的 n 都是常数时间。

坑在哪¶

n 是 9 的倍数时答案是 9 不是 0。直接写 n % 9 会把 9、18、27 全算成 0，必须用 1 + (n-1) % 9 这个偏移写法；
n = 1 时答案 1，公式给 1 + 0 = 1，正确；
题目保证 n >= 1，不用管 n = 0（若要支持，n = 0 的数字根是 0，而公式会给出 1 + (-1) % 9 = 9，需要单独特判）。

样例复核¶

n = 38：38 mod 9 = 2，公式给 1 + 37 % 9 = 1 + 1 = 2，与题面的 38 -> 11 -> 2 一致 ✓。 n = 1：1 + 0 % 9 = 1 ✓。

数位性质与同余见 85-基础数学与递推。

参考实现¶

solutions/BISHI60.py
import sys

n = int(sys.stdin.buffer.read().split()[0])
# 减 1 再取模再加 1：把结果从 {0..8} 平移到 {1..9}，使 9 的倍数落在 9 而不是 0
sys.stdout.write(str(1 + (n - 1) % 9) + "\n")

BISHI60 大水题¶