HDU ACM 題：N^N 的個位數字 - 循環節規律

題目大意

給定 N (1 ≤ N ≤ 10⁹)，求 N^N 的個位數字。多測試用例。

解題思路

個位數字只取決於底數的個位 b = N % 10 及指數 N。各數字冪次個位存在循環節（長度 1、2 或 4）：

指數 N 模循環節長度 c，若餘數為 0 則取第 c 位。計算 b^c % 10 即可。

參考代碼 (C++)

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

int lastDigit(long long n) {
    int b = n % 10;
    if (b == 0 || b == 1 || b == 5 || b == 6) return b;
    int c = (b == 4 || b == 9) ? 2 : 4;
    int exp = n % c; if (exp == 0) exp = c;
    int res = 1;
    for (int i = 0; i < exp; ++i) res = (res * b) % 10;
    return res;
}

int main() {
    int T; cin >> T;
    while (T--) {
        long long n; cin >> n;
        cout << lastDigit(n) << '\n';
    }
    return 0;
}

知識點總結

• 模運算性質：(a*b) % m = ((a%m)*(b%m)) % m。
• 冪次個位循環節長度為 φ(10)=4 的約數（1,2,4）。
• 大指數取模循環節長度即可定位結果。