HDU 1061 Rightmost Digit (快速冪求最後一位)

問題

給定正整數 N (1 ≤ N ≤ 10⁹)，求 N^N 的最後一位數字（個位數）。多測試用例，T ≤ ?。

解法：快速冪取模 10

利用二進制分解指數，維護 result = 1，base = N % 10。當指數最低位為 1 時 result = result * base % 10；每步 base = base * base % 10，指數右移。時間 O(log N)。

代碼 (C++)

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

int modPow(int n) {
    int base = n % 10, exp = n, res = 1;
    while (exp) {
        if (exp & 1) res = (res * base) % 10;
        base = (base * base) % 10;
        exp >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << modPow(n) << '\n';
    }
    return 0;
}

規律觀察 (可選優化)

個位數循環節：

但快速冪已足夠簡潔高效，無需查表。

樣例

輸入：2\n3\n4
輸出：7\n6
解析：3³=27→7，4⁴=256→6。