UVA 10162 Last Digit - 幂次和末位數字週期規律

題目大意

求 S = (1^1 + 2^2 + ... + N^N) mod 10，N 為大整數（最多 100 位）。

週期規律分析

個位數冪次週期

總和週期

每 20 個數為一週期：Σ_{i=1}^{20} i^i mod 10 = 4。
每 100 個數：4 × 5 = 20 ≡ 0 (mod 10)。
⇒ 總和以 100 為週期，且 100 的倍數處和為 0。

演算法

1. 預計算 Z[i] = Σ_{k=1}^i k^k mod 10 (i=1..20)
2. 預計算 Z2[k] = (4k) mod 10 (k=0..4) 為每 20 的塊貢獻
3. 讀 N 為字串，計算 N mod 100
4. 答案 = (Z[N%20] + Z2[N/20]) mod 10

完整程式碼

#include <cstdio>
#include <cstring>

int cyc[10][10], clen[10];
int Z[25], Z2[10] = {0,4,8,2,6};
char s[105];

int mod(char *s, int m) {
    int r = 0;
    for (int i = 0; s[i]; i++) r = (r*10 + s[i]-'0') % m;
    return r;
}

int main() {
    // 預計算各底數週期
    for (int d = 0; d < 10; d++) {
        int v = d; cyc[d][clen[d]++] = d;
        v = v * d % 10;
        while (v != d) { cyc[d][clen[d]++] = v; v = v * d % 10; }
    }
    // 預計算前 20 項前綴和
    for (int i = 1; i <= 20; i++) {
        int d = i % 10, idx = (i % clen[d]) - 1;
        if (idx < 0) idx += clen[d];
        Z[i] = (Z[i-1] + cyc[d][idx]) % 10;
    }
    
    while (scanf("%s", s) == 1 && s[0] != '0') {
        int n100 = mod(s, 100);
        int ans = (Z[n100 % 20] + Z2[n100 / 20]) % 10;
        printf("%d\n", ans);
    }
    return 0;
}

複雜度

• 預計算：O(1)
• 每測資：O(len(N)) 計算模 100
• 空間：O(1)

關鍵點

• 大數模運算逐位處理字串
• 雙層週期：20 和 100
• N=0 為輸入結束標誌