UVA 10515：求 m^n 的個位數 — 規律 + 大數取模

題目

給兩個正整數 m, n (0 ≤ m,n ≤ 10^101)，求 m^n 的最後一位數字。輸入以 0 0 結束。

核心觀察

1. 只看 m 的個位：乘法進位不影響個位，設 k = m % 10。
2. 指數模循環節：
   • 2,3,7,8：循環節 4
   • 4,9：循環節 2
   • 0,1,5,6：循環節 1（恆定）
3. 統一公式：p = (n-1) % 循環節 + 1，但更簡潔：
   取 n 最後兩位作為 d（判斷能否被 4 整除只需看末兩位），
   p = d % 4 == 0 ? 4 : d % 4，
   答案 ans = (k^p) % 10。

大數取模技巧

判斷超長字符串 n 能否被小整數 m 整除：

S[0] = 0;
for i = 1..len: S[i] = (S[i-1]*10 + (n[i]-'0')) % m;
最後看 S[len] == 0。

本題只需 n 末兩位轉整數即可（因 100 能被 4 整除）。

完整代碼（C++）

#include <bits/stdc++.h>
using namespace std;
int main() {
    string m, n;
    while (cin >> m >> n) {
        if (m == "0" && n == "0") break;
        int k = m.back() - '0';
        int d = (n.size() == 1) ? n[0]-'0' : (n[n.size()-2]-'0')*10 + n.back()-'0';
        int p = (d % 4 == 0) ? 4 : d % 4;
        int ans = 1;
        for (int i = 0; i < p; ++i) ans = (ans * k) % 10;
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 時間：O(len(m) + len(n))，實際常數極小。
• 空間：O(1)。

擴展：完整循環節表