题目链接

大水题

题目描述

对于一个数，把它所有位上的数字进行加和，得到新的数。重复执行若干次，直到结果是个位数为止。输出最终的这个个位数。

解题思路

本题要求计算一个整数的“数根”（Digital Root）。这个问题既可以通过直接模拟，也可以通过一个巧妙的数学性质在常数时间内解决。

  1. 模拟法

    最直观的方法是按照题目描述进行模拟：

    • 当给定的数字 大于等于 时，我们进入一个循环。
    • 在循环内部，我们计算 的各位数字之和，并用这个和来更新 。
    • 重复这个过程，直到 变成一个小于 的个位数。

    这个方法是完全可行的，但对于位数非常多的数字，可能需要多次循环。

  2. 数论法（模 9 性质）

    一个更高效、更优雅的方法是利用数论中的一个著名性质：一个非负整数模 的余数与其各位数字之和模 的余数是相同的。

    数学上，对于任意非负整数 ，设 是其各位数字之和，则有：

    由于题目要求反复执行这个过程，这意味着最终得到的那个个位数（即数根）与原始数字 在模 的意义下是同余的。

    由此我们可以推导出结论：

    • 如果 ，其数根就是 。
    • 如果 且是 的倍数（即 ），它的数根是 。
    • 如果 且不是 的倍数，那么它的数根就是 。

    这三种情况可以被一个统一的公式所表达： 对于任意非负整数 ，其数根为 。

    这个公式直接给出了答案，无需循环，时间复杂度为 。

代码

#include <iostream>

using namespace std;

int main() {
    // 读取初始数字
    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);
        }
    }
}

def main():
    # 读取初始数字
    N = int(input())

    # 根据数论公式直接计算并输出结果
    if N == 0:
        print(0)
    else:
        print((N - 1) % 9 + 1)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：数论（数根、模运算）

  • 时间复杂度：。我们使用了一个数学公式直接计算结果，其时间消耗与输入数字 的大小无关。

  • 空间复杂度：。算法只需要常数空间来存储变量。