HDOJ 1163 Eddy's Digital Roots：數字根乘積規律

題目大意

給定正整數 n，計算 n 個 n 相乘後的數字根（Digital Root）。數字根定義為：將數字各位相加，直到結果為個位數。

數學規律推導

設兩位數 ab = 10a + b。其平方：

(10a+b)² = 100a² + 20ab + b²

數字根性質：root(x) ≡ x (mod 9)，且 root(x) ∈ [1,9]（0 特殊處理）。

因此：root(ab × ab) = root( (a+b) × (a+b) ) = root( root(ab) × root(ab) )

推廣結論： 多個數相乘的數字根 = 各數數字根相乘的數字根。即 root(∏ a_i) = root( ∏ root(a_i) )。

算法實現

#include 
using namespace std;

int getRoot(int n) {
    if (n == 0) return 0;
    return (n % 9 == 0) ? 9 : n % 9; // O(1) 公式法
}

int main() {
    int n;
    while (cin >> n && n) {
        int r = getRoot(n);
        int ans = 1;
        for (int i = 0; i < n; i++) {
            ans = getRoot(ans * r); // 利用結論：逐步乘積取數字根
        }
        cout << ans << endl;
    }
    return 0;
}

關鍵點

• 直接模擬大數乘法會溢出，必須利用數字根的同餘性質。
• 公式 `dr(n) = 1 + (n-1) % 9` (n>0) 可 O(1) 計算單個數字根。
• 循環 n 次累乘數字根，中間結果始終 ≤ 9，無溢出風險。