HDU 1013 Digital Roots：數字根的兩種高效算法

問題描述

正整數的數字根：各位數字相加，直到得到一位數。如 24→6，39→12→3。

方法一：字符串模擬

while (gets(s)) {
    if (strcmp(s, "0") == 0) break;
    int sum = 0;
    for (int i = 0; s[i]; i++) sum += s[i] - '0';
    while (sum >= 10) {
        int t = 0;
        while (sum) { t += sum % 10; sum /= 10; }
        sum = t;
    }
    printf("%d\n", sum);
}

方法二：數學公式（9 餘數定理）

數字根 = (n-1) % 9 + 1（n>0 時）

while (scanf("%s", s), strcmp(s, "0")) {
    int sum = 0;
    for (int i = 0; s[i]; i++) sum += s[i] - '0';
    printf("%d\n", (sum - 1) % 9 + 1);
}

原理證明

10 ≡ 1 (mod 9) ⇒ 任何數 ≡ 其各位數字和 (mod 9)。數字根本質是模 9 餘數（0 映射為 9）。

適用場景

• 大整數（超過 64 位）必須用字符串處理
• 普通整數直接用公式 O(1) 計算