HDU 1163 Eddy's Digital Roots - 九餘數定理應用詳解

題目大意

給定正整數 n (n < 10000)，求 n^n 的數字根。數字根定義為將數字各位相加，直到結果為一位數為止。輸入以 0 結束。

核心數學：九餘數定理

一個正整數 N 的數字根等於 N mod 9，若餘數為 0 則數字根為 9（除非 N=0）。因此：

dr(n^n) = (n^n) mod 9，若結果為 0 則輸出 9。

快速冪取模

直接計算 n^n 會溢位，利用模算術性質：

result = 1;
for (int i = 1; i <= n; ++i)
    result = (result * n) % 9;

最後若 result == 0 輸出 9，否則輸出 result。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    while (cin >> n && n) {
        int ans = 1;
        for (int i = 1; i <= n; ++i)
            ans = (ans * n) % 9;
        cout << (ans == 0 ? 9 : ans) << '\n';
    }
    return 0;
}

複雜度

• 時間：O(n) 每測資，n < 10000，極快
• 空間：O(1)

補充說明

若需更高效，可用快速冪 O(log n) 計算 n^n mod 9，但 n 較小時迴圈寫法更簡潔易懂。