HDU 2117 Just a Numble：模擬除法求小數點後第 m 位

問題本質

求 1/n 小數點後第 m 位數字。n≤10^7, m≤10^5。直接模擬手算除法：余數乘 10 除以 n 得商（即該位數字），余數繼續循環。

算法流程

int get_digit(int n, int m) {
    int rem = 1 % n;
    for (int i = 1; i <= m; i++) {
        rem *= 10;
        int digit = rem / n;
        rem = rem % n;
        if (i == m) return digit;
        if (rem == 0) return 0; // 有限小數提前結束
    }
    return 0;
}

關鍵點

• 無需存儲所有位，只保留當前余數，空間 O(1)。
• 若余數變 0，後續全為 0，可直接跳出返回 0。
• 循環小數自動處理：余數必在 [1, n-1] 循環，但只需跑到第 m 步即可。

完整代碼

#include <iostream>
using namespace std;
int main() {
    int n, m;
    while (cin >> n >> m) {
        int rem = 1 % n, digit = 0;
        for (int i = 1; i <= m; i++) {
            rem *= 10;
            digit = rem / n;
            rem %= n;
            if (rem == 0) { digit = 0; break; }
        }
        cout << digit << endl;
    }
    return 0;
}

複雜度

時間 O(m)，最多 10^5 步，極快。空間 O(1)。