题解 P1530 【分数化小数 Fractions to Decimals】

· · 题解

upd 2020/7/29 已修改代码中的错误

这是道有点复杂的模拟题

主要思路：长除

先得到整数部分存着暂时不管

处理N % D

主要思路：

如果长除中得到了一个之前出现过的结果 那么一定出现了循环节 所以把每一个余数出现的位置（初始值设为-1）都保存下来 如果发现一个余数的出现位置不是-1 那就找到了循环节 把循环节头尾记录下来

把小数部分每一位存下来 没有必要把不循环部分和循环部分分开来处理

模拟一下样例？

45 56 - 0
        .
8 2   - 8
0 20  - 0 
3 32  - 3
5 40  - 5
7 8   - 7
1 24  - 1 
4 16  - 4
2 48  - 2 
8 32  - 8
(5 40 - 5)
32出现过 571428为循环节

76个字符一换行 这个其实不算最恶心的输出格式了。。

存一个sum 先加上1（小数点） 加上整数部分位数（这个一定小于76 不用判）

然后 出一个字符sum++ sum只要加就判

详见代码

#include <bits/stdc++.h>
using namespace std;
int apr[100005] = {0}; //apr[i]表示余数i第一次出现的位置
int zs;
int xs[100005] = {0}; //xs[i]代表除下来结果小数部分第i位（从0开始）
//循环节最长为D-1 所以开100000+5就够了
int ans = 0,tmp,flag = 0;
int sum = 0; //sum记录目前已输出多少个字符
int main() {
    int a,b,c,d;
    scanf("%d %d",&a,&b);
    memset(apr,-1,sizeof(apr));
    //正文开始
    zs = a / b; //整数部分
    c = a % b; //拿余数继续处理
    while(1) {
        if(apr[c] != -1) { //如果该余数之前出现过 就代表循环节已经出现了 把ans变为循环节起始位置，tmp是终止位置
            tmp = ans;
            ans = apr[c];
            break;
        }
        apr[c] = ans;
        c = c * 10; 
        d = c / b;
        c = c % b;
        xs[ans] = d; //长除过程
        ans ++; //ans表示当前正在处理第几位（从0开始）
        if(c == 0) { //余数为零代表除尽 立个flag flag=1表示没有循环节
            flag = 1;
            break;
        }
    }
    //正文结束，后面全是处理76个一换行
    printf("%d.",zs);
    sum ++;
    while(1) {
        sum ++;
        zs = zs / 10;
        if(zs == 0) break;
    }
    for(int i = 0; i < ans; i ++) {
        printf("%d",xs[i]);
        sum ++;
        if(sum % 76 == 0) {
            printf("\n");
        }
    }
    if(flag == 0) { //存在循环节
        printf("(");
        sum ++;
        if(sum % 76 == 0) {
            printf("\n");
        }
        for(int i = ans; i < tmp; i ++) {
            printf("%d",xs[i]);
            sum ++;
            if(sum % 76 == 0) {
                printf("\n");
            }
        }
        printf(")");
        sum ++;
        if(sum % 76 == 0) {
            printf("\n");
        }
    }
    return 0;
}