题解 | #大水题#

题目链接

HIGH11 大水题

题目描述

给定一个非负整数 n。反复地将 n 的各位数字相加，直到结果是一个一位数。请你输出这个最终的一位数。

解题思路

这个问题要求计算一个数的“数根”（Digital Root）。有两种主要的方法可以解决它：模拟法和数学法。

方法一：模拟法

这是最直观的方法。我们完全按照题目描述的过程来执行：

启动一个循环，条件是当前的数 n 大于等于 10（即它不是一位数）。
在循环内部，再用一个循环计算 n 的各位数字之和，存入一个临时变量 sum。
将 n 的值更新为 sum。
当外层循环结束时，n 就是我们要求的一位数。

这种方法简单易懂，但对于非常大的数，可能需要多次迭代，效率稍低。

方法二：数学法（求数根）

这个过程实际上是在求 n 对 9 取模的结果，但有一些特殊情况。一个数 n 的数根与其对 9 取模的结果有如下关系：

n = d_k * 10^k + ... + d_1 * 10^1 + d_0 * 10^0
n mod 9 = (d_k * (9+1)^k + ... + d_1 * (9+1) + d_0) mod 9
根据二项式定理和模运算性质，(9+1)^k mod 9 = 1^k mod 9 = 1。
因此，n mod 9 = (d_k + ... + d_1 + d_0) mod 9。
这意味着，一个数与它的各位数字之和，对于模 9 是同余的。

这个性质可以推广：反复对各位数字求和，直到得到一位数，这个结果就是原始数字对 9 取模的结果。

基于此，我们可以推导出数根 dr(n) 的公式：

如果 n = 0，则数根为 0。
如果 n > 0 且 n % 9 == 0，则数根为 9。（例如 9, 18, 27... 的数根都是9）
如果 n > 0 且 n % 9 != 0，则数根就是 n % 9。

这三种情况可以统一为一个非常优美的公式：dr(n) = (n - 1) % 9 + 1（此公式对 n>0 成立）。

当 n=18 时, (18-1)%9 + 1 = 17%9 + 1 = 8 + 1 = 9。
当 n=38 时, (38-1)%9 + 1 = 37%9 + 1 = 1 + 1 = 2。

这种方法不需要任何循环，可以直接通过一次计算得出结果，效率极高。

代码

cpp
java
python

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n;
    cin >> n; // 只读取一次输入

    if (n == 0) {
        cout << 0 << endl;
    } else {
        cout << (n - 1) % 9 + 1 << endl;
    }
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong(); // 只读取一次输入
        
        if (n == 0) {
            System.out.println(0);
        } else {
            System.out.println((n - 1) % 9 + 1);
        }
    }
}

# 读取单次输入
n = int(input())

if n == 0:
    print(0)
else:
    print((n - 1) % 9 + 1)

算法及复杂度

算法：数论、模运算
时间复杂度： $\mathcal{O}(1)$ 。对于每个输入，我们都只需要进行一次数学运算。
空间复杂度： $\mathcal{O}(1)$ 。