C 語言實現分數轉循環小數：高精度除法與循環節檢測完整算法

題目要求

輸入分數 N/D，輸出小數形式。循環節用括號括起。例：1/3=. (3)，41/333=. (123)，45/46=. 9(7826086956521739130434)。

核心原理

1. 整數部分：`N / D` 直接輸出。
2. 非循環小數部分：分母去除因子 2、5（乘 5/2 變 10），每步輸出一位。
3. 純循環部分：剩餘分母僅含 2、5 以外因子。利用 `999...9 / D * N` 的高精度除法求循環節。

完整 C 代碼（高精度模擬）

#include <stdio.h>
#include <string.h>

#define LEN 100          // 高精度分段數
#define BASE 10000       // 每段 4 位十進制

// 高精度取模：K 為大整數（BASE 進制），返回 K % D
int modBig(int *K, int D) {
    int rem = 0;
    for (int i = LEN - 1; i >= 0; i--) {
        rem = (rem * BASE + K[i]) % D;
    }
    return rem;
}

// 高精度乘 10 並加 9：K = K * 10 + 9
void mul10Add9(int *K) {
    int carry = 9;
    for (int i = 0; i < LEN; i++) {
        long long cur = (long long)K[i] * 10 + carry;
        K[i] = cur % BASE;
        carry = cur / BASE;
    }
}

// 高精度輸出 K / D * N 的循環節數字
void printCirc(int *K, int D, int N) {
    int digits[LEN] = {0};
    int rem = 0;
    for (int i = LEN - 1; i >= 0; i--) {
        long long cur = (long long)rem * BASE + K[i];
        digits[i] = cur / D;
        rem = cur % D;
    }
    // 乘 N
    int carry = 0;
    for (int i = 0; i < LEN; i++) {
        long long cur = (long long)digits[i] * N + carry;
        digits[i] = cur % BASE;
        carry = cur / BASE;
    }
    // 輸出（跳過前導 0）
    int started = 0;
    for (int i = LEN - 1; i >= 0; i--) {
        if (!started) {
            if (digits[i] == 0) continue;
            printf("%d", digits[i]);
            started = 1;
        } else {
            printf("%04d", digits[i]); // 補齊 4 位
        }
    }
    if (!started) printf("0");
}

int main() {
    int N, D;
    scanf("%d %d", &N, &D);
    
    // 整數部分
    if (N >= D) {
        printf("%d", N / D);
        N %= D;
    }
    printf(".");
    
    // 非循環部分：去除分母因子 2、5
    while (D % 2 == 0 || D % 5 == 0) {
        if (D % 10 == 0) { D /= 10; if (N % 10 == 0) N /= 10; }
        else if (D % 2 == 0) { N *= 5; D *= 5; }
        else { N *= 2; D *= 2; }
        if (N >= D) { printf("%d", N / D); N %= D; }
        else printf("0");
    }
    
    // 純循環部分
    if (N != 0) {
        printf("(");
        int K[LEN] = {0};
        K[0] = 9; // 起始 9
        while (modBig(K, D) != 0) mul10Add9(K); // 構造 99...9 能被 D 整除
        printCirc(K, D, N);
        printf(")");
    }
    printf("\n");
    return 0;
}

關鍵點

• **不能用浮點數**，必須用整數高精度模擬筆算除法。
• 循環節來源於分母含 2、5 以外因子；長度 ≤ φ(D) (歐拉函數)。
• 代碼中 `BASE=10000`、`LEN=100` 可處理 D < 10000、循環節 ≤ 400 位，足夠題目範圍。
• 輸出格式嚴格：整數部分、小數點、非循環位、括號包裹循環節。