题解：UVA275 Expanding Fractions

· · 题解

题目大意

对于给定的两个整数 n 和 m（1 \le n, m \le 3000），计算分数 \frac{n}{m} 的十进制小数表示，找出循环节（若存在）并按要求格式输出。

算法思路

本题本质上是模拟除法运算，并判断循环节。
核心观察：在长除法过程中，余数 r 的范围是 0 \le r < m。若某个余数重复出现，则后续的小数位也会重复，即进入循环节。
我们可以用数组 pos[r] 记录余数 r 第一次出现时对应的小数位数，从而在余数重复时确定循环节的起点。

步骤如下：

  1. 计算小数点后的第一位余数 r = n \bmod m。
  2. 初始化 pos 数组为 -1（表示余数未出现过），pos[r] = 0。
  3. 重复以下过程直到余数 r 为 0（有限小数）或余数 r 重复出现：
    • r \gets r \times 10
    • 当前小数位 digit = \lfloor r / m \rfloor
    • 将 digit 存入 dis 数组
    • r \gets r \bmod m
    • 若 r = 0，则为有限小数，结束
    • 若 pos[r] \neq -1，则从 pos[r] 开始到当前位之前为循环节，结束
    • 否则记录 pos[r] = 当前小数位数
  4. 按格式输出结果。

代码实现


#include <bits/stdc++.h>
using namespace std;

const int N = 3005;

int pos[N];
int dt[N * 2];

int main() {
    int n, m;
    while (cin >> n >> m && (n || m)) {
        memset(pos, -1, sizeof(pos));
        int r = n % m;
        int len = 0; 
        int start = -1, End = -1;
        pos[r] = 0;
        while (1) {
            r *= 10;
            dt[len] = r / m;
            r %= m;
            len++;
            if (r == 0) { 
                break;
            }
            if (pos[r] != -1) {
                start = pos[r];
                End = len - 1;
                break;
            }
            pos[r] = len;
        }

        cout << ".";
        for (int i = 0; i < len; i++) {
            if (i > 0 && i % 50 == 0) {
                cout << endl; 
            }
            cout << dt[i];
        }
        cout << endl;

        if (r == 0) {
            cout << "This expansion terminates." << endl;
        } else {
            int len = End - start + 1;
            cout << "The last " << len << " digits repeat forever." << endl;
        }
    }
    return 0;
}