洛谷P1530 分数化小数 Fractions to Decimals

- 103通过
- 348提交
题目提供者该用户不存在
标签USACO
难度普及/提高-

讨论题解

题目描述

写一个程序，输入一个形如N/D的分数(N是分子，D是分母)，输出它的小数形式。如果小数有循环节的话，把循环节放在一对圆括号中。

例如, 1/3 =0.33333333写成0.(3), 41/333 = 0.123123123...写成0.(123), 用xxx.0 等表示整数。典型的转化例子：

1/3 = 0.(3)
22/5 = 4.4
1/7 = 0.(142857)
2/2 = 1.0
3/8 = 0.375
45/56 = 0.803(571428)
PROGRAM NAME fracdec

输入输出格式

输入格式：

单独的一行包括被空格分开的N和D(1 <= N,D <= 100000)。

输出格式：

按照上面规则计算出的小数表达式.如果结果长度大于76,每行输出76个字符.

输入输出样例

输入样例#1：

45 56

输出样例#1：

0.803(571428)

说明

翻译来自NOCOW

USACO 2.4

分析：看着和数学有关，其实是一道大模拟......细节非常多:

1.因为要76行一输出，所以要先用一个变量记录长度，小数点也要加上去.

2.如果能够除尽，直接输出答案即可.

3.对于整数部分的长度，不断除以10，直到等于0，每次除的时候累加长度.

4.如果除以10恰好等于0，那么长度+1.

然后就是小数部分的处理了，难点是循环节的处理，如果一个余数之前恰好出现过，而当前的除数正好是之前余数对应的除数，那么就出现循环节，这里用两个数组记录，一个记录上一个相同余数位置，一个记录除数.

最后输出的时候判断累加的长度是否为76，是则换行即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
int n,d,a[1000010],check[1000010],tot1 = 1,tot,ans[1000010],cur[1000010],h[100010],integer[1000110],remainder[1000101],flag,l,r;

int main()
{
    scanf("%d%d",&n,&d);
    if (n % d == 0)
    {
        printf("%d.0
",n/d);
        return 0;
    }
    printf("%d.",n/d);
    int temp = n / d; 
    while (temp)
    {
        tot1++;
        temp /= 10;
    }
    if (n / d == 0)
    tot1++;
    remainder[0] = n % d;
    while (1)
    {
        tot++;
        integer[tot] = remainder[tot - 1] * 10 / d;
        remainder[tot] = remainder[tot - 1] * 10 % d;
        if (remainder[tot] == 0)    
            break;
        if (cur[remainder[tot]] > 0 && h[cur[remainder[tot]]] == integer[tot])
        {
            l = cur[remainder[tot]];
            r = tot - 1;
            break;
        }
        cur[remainder[tot]] = tot;
        h[cur[remainder[tot]]] = integer[tot];
    }
    for (int i = 1; i <= tot; i++)
    {
        if (i == l)
        {
            printf("(");
            tot1++;    
        }
        printf("%d",integer[i]);
        tot1++;
        if (i == r)
        {
            printf(")");
            break;
        }
        if (tot1 % 76 == 0)
        printf("
");
    }
    printf("
");
    
    return 0;
}