ZeroJudge 解題筆記：c084. 00275 - Expanding Fractions

作者：王一哲
日期：2026年2月21日


ZeroJudge 題目連結：c084. 00275 - Expanding Fractions

解題想法

這題要依序處理每個位數相除的結果，如果無法整除時要將餘數乘以 10 再繼續往下除，同時記錄每個餘出現過的位置，直到先找循環節的終點為止。最後還要依照題目要求的格式輸出答案。

Python 程式碼

使用時間約為 9 ms，記憶體約為 3.1 MB，通過測試。

import sys

def divid(a, b):  # a < b, 計算 a/b
    dec_part = []  # 小數部分
    repeat_start = -1  # 循環小數起點
    rem = a  # 餘數，由於題目限制 a < b，初始值為 a
    rem_pos = dict()  # 用字典儲存出現過的餘數位置
    while rem != 0:  # 如果無法整除繼續執行
        if rem in rem_pos:  # 如果這個餘數已經出現過
            repeat_start = rem_pos[rem]  # 設定循環的起點
            break  # 中止迴圈
        rem_pos[rem] = len(dec_part)  # 記錄這個餘數的位置
        rem *= 10  # 將餘數放大為 10 倍
        dec_part.append(str(rem//b))  # 小數部分加一位
        rem %= b  # 新的餘數
    ans = "." + "".join(dec_part)  # 要輸出的答案
    for i in range(0, len(ans), 50):  # 逐行輸出，每行最多 50 個字元
        print(ans[i:i+50])
    if repeat_start == -1:  # 不循環
        print("This expansion terminates.")
    else:  # 循環
        print(f"The last {len(dec_part)-repeat_start:d} digits repeat forever.")

for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    divid(n, m)

如果題目改成要計算相除的小數並標示循環節，可以這樣寫。

import sys

def divid(a, b):  # a < b, 計算 a/b
    int_part = str(a//b)  # 整數部分
    rem = a%b  # 餘數
    """ 特例，可以整除，回傳整數部分 """
    if rem == 0: return int_part
    """ 繼續處理小數部分 """
    dec_part = []  # 小數部分
    repeat_start = -1  # 循環小數起點
    rem_pos = dict()  # 用字典儲存出現過的餘數位置
    while rem != 0:  # 如果無法整除繼續執行
        if rem in rem_pos:  # 如果這個餘數已經出現過
            repeat_start = rem_pos[rem]  # 設定循環的起點
            break  # 中止迴圈
        rem_pos[rem] = len(dec_part)  # 記錄這個餘數的位置
        rem *= 10  # 將餘數放大為 10 倍
        dec_part.append(str(rem//b))  # 小數部分加一位
        rem %= b  # 新的餘數
    if repeat_start == -1:  # 不循環
        return int_part + "." + "".join(dec_part)
    else:  # 循環，用 () 標示循環節
        return int_part + "." + "".join(dec_part[:repeat_start]) \
               + "(" + "".join(dec_part[repeat_start:]) + ")"

for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    print(divid(n, m))

C++ 程式碼

使用時間約為 2 ms，記憶體約為 380 kB，通過測試。

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

void divid(int a, int b) {
    int rem = a, repeat_start = -1;
    map<int, int> rem_pos;
    string dec_part = "";
    while(rem != 0) {
        if (rem_pos.find(rem) != rem_pos.end()) {
            repeat_start = rem_pos[rem];
            break;
        }
        rem_pos[rem] = (int)dec_part.size();
        rem *= 10;
        dec_part += to_string(rem/b);
        rem %= b;
    }
    string ans = "." + dec_part;
    int lena = (int)ans.size();
    for(int i=0; i<lena; i+=50) {
        cout << ans.substr(i, 50) << "\n";
    }
    if (repeat_start == -1) {
        cout << "This expansion terminates.\n";
    } else {
        cout << "The last " << (int)dec_part.size() - repeat_start << " digits repeat forever.\n"; 
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    while(cin >> n >> m) {
        if (n == 0 && m == 0) break;
        divid(n, m);
    }
    return 0;
}

如果題目改成要計算相除的小數並標示循環節，可以這樣寫。

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

string divid(int a, int b) {
    string int_part = to_string(a/b);
    int rem = a%b;
    /* 特例，可以整除，回傳整數部分 */
    if (rem == 0) return int_part;
    /* 繼續處理小數部分 */
    int repeat_start = -1;
    map<int, int> rem_pos;
    string dec_part = "";
    while(rem != 0) {
        if (rem_pos.find(rem) != rem_pos.end()) {
            repeat_start = rem_pos[rem];
            break;
        }
        rem_pos[rem] = (int)dec_part.size();
        rem *= 10;
        dec_part += to_string(rem/b);
        rem %= b;
    }
    if (repeat_start == -1) {
        return int_part + "." + dec_part;
    } else {
        return int_part + "." + dec_part.substr(0, repeat_start) + 
               "(" + dec_part.substr(repeat_start) + ")";
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    while(cin >> n >> m) {
        if (n == 0 && m == 0) break;
        cout << divid(n, m) << "\n";
    }
    return 0;
}