HDU 1061 Rightmost Digit：快速冪求 n^n 末位數字

問題簡化

求 n^n 的個位數字，即 n^n mod 10。
n 可達 2^31-1，直接算必溢出，需用模運算性質：
(a × b) mod m = [(a mod m) × (b mod m)] mod m

快速冪模板

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

原始代碼的遞歸寫法與改進

// 原始遞歸版
ll pow_mod(ll k) {
    if (k == 1) return n % MOD;
    ll a = pow_mod(k / 2);
    ll ans = a * a % MOD;
    if (k % 2) ans = ans * n % MOD;
    return ans;
}

// 主函數中
ll ans = pow_mod(n);
while (ans > 10) ans %= 10; // 多餘操作，直接 ans %= 10 即可
printf("%lld\n", ans);

優化要點

• 模數可直接設 10：MOD = 10，無需最後循環取模
• 迭代版更優：避免遞歸棧開銷，常數更小
• 類型注意：n 可能超 32 位，用 long long

完整優化代碼

#include 
using namespace std;

typedef long long ll;

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

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

數學洞察：循環節進一步優化

個位數字只有 0-9，n^n mod 10 只依賴 n mod 10 和 n mod 4（歐拉定理 φ(10)=4）。
可預計算 10×4=40 種情況的查表，O(1) 回答。但快速冪 O(log n) 已足夠快（log₂(2³¹) ≈ 31 步）。

總結

• 核心：模運算分配律 + 二進制快速冪
• 模板：迭代版 mod_pow(base, exp, mod)
• 應用：任意大數冪取模、矩陣快速冪、線性遞推加速