分数化小数

题目描述

输入一个分数 $N/D$ （ $1 \leqslant N, D \leqslant 100000$ ），输出它的小数形式：循环节用一对圆括号括起来（如 $1/3$ 写成 0.(3)），整数写成 xxx.0。输出串长度超过 76 个字符时，每 76 个字符换一行。样例输入：45 56；样例输出：0.803(571428)。

思路

模拟竖式长除法：每一步的商位由当前余数唯一决定，用数组登记每个余数第一次出现时已写出的小数位数。余数变 0 就是有限小数（一位没写补 0）；某个余数第二次出现时，它第一次出现的位置之后就是循环节，加上括号即可。余数只有 $D$ 种取值， $O(D)$ 步内必然终止。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 04:30
# update_at: 2026-10-01 04:30

import sys


def long_division_digits(n: int, d: int) -> str:
    """模拟 n/d 的长除法：返回整数部分、纯小数部分和循环节起点。

    余数每出现一次就登记它的位数；同一个余数第二次出现的位置
    就是循环节的起点，这保证总步数不超过 d（余数只有 d 种取值）。
    """
    seen: dict[int, int] = {}  # 余数 -> 它出现时已在小数部分写下的位数
    digits: list[str] = []     # 小数点后的数字串
    r = n % d                  # 当前余数，0 表示已经除尽
    while r and r not in seen:
        seen[r] = len(digits)
        r *= 10
        digits.append(str(r // d))
        r %= d

    body = ''.join(digits[: seen[r]]) + '(' + ''.join(digits[seen[r]:]) + ')' if r else ''.join(digits)
    return f'{n // d}.{body or "0"}'


def solve() -> None:
    n, d = map(int, sys.stdin.buffer.read().split())
    text = long_division_digits(n, d)
    print('\n'.join(text[i:i + 76] for i in range(0, len(text), 76)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:11
 * update_at: 2026-10-06 10:11
 */
// main.cpp：模拟竖式长除法，把分数 N/D 化成小数并标记循环节。
#include <cstdio>

typedef long long ll;

const int MAXD = 100005;

int seen[MAXD];    // seen[r] = 余数 r 第一次出现时已写出的小数位数（-1 表示还没出现）
char digits[MAXD]; // 小数点后依次写出的每一位数字
ll cnt;            // 已写出的小数位数

ll n, d;

int main() {
    scanf("%lld %lld", &n, &d);
    for (ll i = 0; i < d; i++) seen[i] = -1;

    ll r = n % d; // 长除法当前余数，余数决定之后的所有商位
    ll k = -1;    // 循环节起点：余数重复时等于它第一次出现的位置，-1 表示除尽
    while (r != 0) {
        if (seen[r] != -1) { // 这个余数出现过，之后每一步都会重复
            k = seen[r];
            break;
        }
        seen[r] = cnt;      // 登记余数出现时已写出的位数
        r = r * 10;
        digits[cnt++] = '0' + r / d; // 本位商
        r = r % d;
    }

    // 组装完整输出串：整数部分 + '.' + 小数部分（循环节加括号）
    char ans[MAXD + 30];
    ll len = snprintf(ans, sizeof(ans), "%lld.", n / d);
    if (k == -1) {
        if (cnt == 0) ans[len++] = '0'; // 整数情形必须写成 x.0
        for (ll i = 0; i < cnt; i++) ans[len++] = digits[i];
    } else {
        for (ll i = 0; i < k; i++) ans[len++] = digits[i]; // 不循环部分
        ans[len++] = '(';
        for (ll i = k; i < cnt; i++) ans[len++] = digits[i]; // 循环节
        ans[len++] = ')';
    }
    ans[len] = '\0';

    // 每 76 个字符一行输出（换行符不占 76 个字符的名额）
    for (ll i = 0; i < len; i++) {
        putchar(ans[i]);
        if ((i + 1) % 76 == 0) putchar('\n');
    }
    putchar('\n');
    return 0;
}

目录

题目描述

思路

参考代码