HDU 1061 Rightmost Digit 題解：快速冪求 N^N 末位數字

問題描述

給定整數 N (1 ≤ N ≤ 10^9? 題目未給上限但樣例暗示較大)，求 N^N 的最右位數字（即個位數字）。多測試用例。

數學觀察

只關心個位，故只需計算 `(N mod 10)^N mod 10`。即底數模 10 後再做模 10 指數運算。

算法：模 10 快速冪

遞歸/迭代實現 `pow_mod(base, exp, mod)`：

• `base = N % 10`
• `exp = N`
• `mod = 10`
• 利用 `a^b mod m = (a^(b/2) mod m)^2 * (b%2? a:1) mod m`

AC 代碼 (C)

#include <stdio.h>

int mod_pow(int base, int exp, int mod) {
    int res = 1;
    while (exp) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        printf("%d\n", mod_pow(n % 10, n, 10));
    }
    return 0;
}

遞歸版（原代碼風格）

int rightMost(int n, int N) { // n: 指數, N: 底數
    if (n == 0) return 1;
    int t = rightMost(n / 2, N);
    t = t * t % 10;
    if (n % 2) t = t * N % 10;
    return t;
}
// 調用: rightMost(n, n%10)

關鍵點

• **模 10 封閉性**：任意整數乘積的個位僅由各因子個位決定。
• **指數不取模**：費馬小定理/歐拉定理要求模數與底數互質，模 10 非質數且底數可能為偶數或 5，故**不能**將指數模 φ(10)=4。必須用原始指數 N 做快速冪。
• **遞歸深度**：log₂(N) ≤ 30 (N≤10⁹)，棧安全。

複雜度

每測試用例 O(log N) 時間，O(log N) 遞歸棧空間（或 O(1) 迭代）。極快。

總結

HDU 1061 是模冪運算的入門題。核心是識別「只需個位」→「底數模 10」→「快速冪取模 10」。注意**指數不可取模**，這是新手常見錯誤。迭代版本更穩健，推薦生產使用。