ACM 題目：求整數後 n-1 位數字 (C 語言解法)

題目描述

給定無號整數 w (10 < w ≤ 1,000,000)，設 w 為 n 位數 (n ≥ 2)，求其後 n-1 位組成的數字（忽略前導零）。若除最高位外全為 0，輸出 0。

範例

輸入：
4
1023
5923
923
1000

輸出：
23
923
23
0

解題思路

1. 計算 w 的位數 n：反覆除以 10 直到為 0，計數器遞增。
2. 計算 10^(n-1) 作為除數 div。
3. 結果為 w % div (取模運算)。

完整代碼

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

int main() {
    int M;
    scanf("%d", &M);
    while (M--) {
        int w;
        scanf("%d", &w);
        int t = w, n = 0;
        while (t) { t /= 10; n++; }        // 計算位數 n
        int div = (int)pow(10, n - 1);     // 10^(n-1)
        printf("%d\n", w % div);           // 取後 n-1 位
    }
    return 0;
}

邊界情況處理

• w = 1000 → n=4, div=1000, 1000%1000=0 ✓
• w = 10 → n=2, div=10, 10%10=0 ✓
• w = 999999 → n=6, div=100000, 999999%100000=99999 ✓

優化版 (避免浮點 pow)

int div = 1;
while (div <= w / 10) div *= 10; // 整數乘法求 10^(n-1)
printf("%d\n", w % div);

此法僅用整數運算，無 math.h 依賴，效能更佳。

複雜度分析

• 時間：O(log₁₀ w) ≈ 最多 7 次迴圈 (w ≤ 1,000,000)
• 空間：O(1)