HDU 1097 A hard puzzle：冪次末位數字的循環節規律

題目大意

給定 a, b，求 a^b 的最後一位數字（即 a^b mod 10）。多組測試，直到 EOF。

核心規律：末位數字循環節

對於任意整數 a，其冪次末位數字隨指數增長呈現週期性，週期長度 ≤ 4。
預計算 a%10 的冪次末位序列，直到重複初值，即得循環節。
答案為 cycle[b % cycle_len]（注意 b % cycle_len == 0 取最後一位）。

各數字循環節表

C++ 參考代碼

int main() {
    long long a, b;
    while (cin >> a >> b) {
        a %= 10;
        if (b == 0) { cout << 1 << endl; continue; }  // a^0 = 1
        int cycle[4], len = 0;
        int cur = a;
        do {
            cycle[len++] = cur;
            cur = (cur * a) % 10;
        } while (cur != a);
        cout << cycle[(b - 1) % len] << endl;
    }
    return 0;
}

關鍵點

• b=0 特判：a^0 = 1（題目未明確但通常需處理）。
• 循環節檢測：do-while 確保至少一個元素。
• 索引計算：(b-1) % len 因序列從指數 1 開始。
• 輸入範圍大時用 long long 讀取 b。

進階：快速冪取模通用模板

int mod_pow(int a, long long b, int mod) {
    int res = 1;
    a %= mod;
    while (b) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
// 直接調用 mod_pow(a, b, 10) 即可，O(log b) 同樣極快。