题意分析

本题要求对给定的两个整数进行除法运算，打印出其小数展开式。若小数展开是有限的，需完整打印；若为无限循环小数，要打印到循环模式首次重复前的数字。同时，输出需按每行 50 个字符（最后一行除外）进行排版，最后需说明小数展开是有限的还是无限循环的，若是无限循环，要给出循环节的数字个数。

解题思路

1. 输入处理：
   • 程序通过 while (scanf("%d%d", &a, &b) == 2) 循环读取输入，直到输入的分子 a 和分母 b 都为 0 时停止。
2. 小数展开计算：
   • 初始化一个数组 vis 用于记录每个余数第一次出现时的位置，初始值都设为 -1。
   • 从被除数 a 开始，将其乘以 10 后除以 b，得到商作为当前小数位的数字并输出。
   • 计算新的余数 a % b，检查该余数是否在之前出现过（即 vis[a % b] >= 0）。若出现过，则说明找到了循环节，循环节的长度为当前步数 cnt 减去该余数首次出现的步数 vis[a % b]。
   • 若余数为 0，则说明小数展开是有限的。
3. 输出格式处理：
   • 每输出一个小数位，计数器 t 加 1。当 t 达到 49 或者 t > 49 且 (t + 1) % 50 == 0 时，进行换行操作。
   • 最后根据是否找到循环节输出相应的提示信息。

代码实现

//poj 1140
//sep9
#include<iostream>
using namespace std;
int vis[1024];

void solve(int a, int b)
{
    int cnt = 0, t = 0;
    // 将 memset 替换为循环初始化
    for (int i = 0; i < 1024; ++i) {
        vis[i] = -1;
    }
    vis[a] = cnt++;
    a *= 10;
    printf(".");
    while (1) {
        printf("%d", a / b);
        ++t;
        if (t == 49 || (t > 49 && (t + 1) % 50 == 0))
            puts("");
        if (vis[a % b] >= 0) {
            if (!(t == 49 || (t > 49 && (t + 1) % 50 == 0)))
                puts("");
            printf("The last %d digits repeat forever.\n", cnt - vis[a % b]);
            return;
        }
        vis[a % b] = cnt++;
        a = a % b * 10;
        if (a == 0) {
            if (!(t == 49 || (t > 49 && (t + 1) % 50 == 0)))
                puts("");
            printf("This expansion terminates.\n");
            return;
        }
    }
}

int main()
{
    int a, b;
    while (scanf("%d%d", &a, &b) == 2) {
        if (a == 0 && b == 0)
            break;
        solve(a, b);
    }
    return 0;
}

复杂度分析

• 时间复杂度：由于在循环模式重复之前的数字个数永远不会超过分母的值，因此时间复杂度为 $O(b)$，其中 $b$ 是分母。
• 空间复杂度：使用了一个大小为 1024 的数组 vis 来记录余数的出现位置，因此空间复杂度为 $O(1)$。