HDU 1097 解題報告：a^b 末位數字規律與快速冪取模

HDU 1097 解題報告：a^b 末位數字規律與快速冪取模

HDU 1097 要求計算 a^b 的個位數字。利用模 10 運算的週期性，可在 O(1) 時間解決，無需大數運算。

數學規律

任意整數 a 的冪次個位數字隨指數 b 以 **4 為週期** 循環 (0,1,5,6 為週期 1)。

a 末位 | 循環序列 (b=1,2,3,4,5...)
0      | 0,0,0,0...
1      | 1,1,1,1...
2      | 2,4,8,6,2...
3      | 3,9,7,1,3...
4      | 4,6,4,6...
5      | 5,5,5,5...
6      | 6,6,6,6...
7      | 7,9,3,1,7...
8      | 8,4,2,6,8...
9      | 9,1,9,1...

解題公式

1. x = a % 10 取個位
2. n = b % 4 取指數模 4
3. 若 n == 0 則用第 4 位 (即 x^4 % 10)，否則用第 n 位 (x^n % 10)

完整 C 代碼

#include <stdio.h>
#include <math.h>

int last_digit(int a, int b) {
    int x = a % 10;
    int n = b % 4;
    int p = (n == 0) ? 4 : n;
    // 直接計算 x^p % 10，p≤4 絕不溢位
    int res = 1;
    for (int i = 0; i < p; i++) res = (res * x) % 10;
    return res;
}

int main() {
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF) {
        printf("%d\n", last_digit(a, b));
    }
    return 0;
}

關鍵優化點

• 避免 pow() 浮點誤差，用整數迴圈乘法取模
• 指數 b 可能極大 (題目未給上限)，模 4 運算 O(1)
• 多組測資直到 EOF，while(scanf(...)!=EOF)

擴展：快速冪模板 (通用 a^b % mod)

long long mod_pow(long long a, long long b, long long mod) {
    long long res = 1 % mod;
    a %= mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
// HDU 1097 即 mod_pow(a, b, 10)

複雜度分析

• 時間：O(1) (週期法) 或 O(log b) (快速冪)
• 空間：O(1)

此題核心考察「模運算週期性」與「快速冪」兩大數論基礎工具，是 ACM 入門必刷經典題。