#P1140. Expanding Fractions

    ID: 141 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>字符串数据结构East Central North America 1994

Expanding Fractions

题目描述(Description)

在这个问题里,你要负责打印出两个整数相除所得结果的小数展开式。正如你所熟知的,很多整数相除后的小数展开会出现循环的数字序列,也就是循环节。你必须要找出这些循环节。你需要打印出给定整数商的小数展开形式,当小数展开结束,或者当循环模式即将首次重复的时候停止打印。要是存在循环模式,你得说明循环模式中数字的个数。

输入格式(Input)

输入由多个测试实例构成,每个实例都由一行中的两个正整数组成。第一个整数代表分数的分子,第二个整数代表分数的分母。在本题中,分子始终小于分母,并且分母小于10001000。当分子和分母都为00时,输入结束。

输出格式(Output)

对于每一个输入实例,输出应该是分数的小数展开形式,并且以小数点开头。如果小数展开是有限的,你应当打印出完整的小数展开。要是小数展开是无限的,你需要打印出小数展开,直到但不包含循环模式首次重复的那个数字。

举个例子,44除以1111等于.3636363636.3636363636…,应该打印成.36.36。(请注意,要找到最短的循环模式。在上述例子中,36363636363636363636等等都是循环模式,但最短的循环模式是3636。)

由于有些小数展开可能会很长,多行展开时每行应正好包含5050个字符(最后一行除外,最后一行当然可能更短),这其中包含开头的小数点。

在小数展开的最后一行的下一行,应该有一行文字,内容要么是“This expansion terminates.”(意思是这个展开是有限的),要么是“The last n digits repeat forever.”(意思是最后nn个数字无限循环,这里的nn是循环模式中数字的个数)。

有用的提示:在循环模式重复之前的数字个数永远不会超过分母的值。

3 7
345 800
112 990
53 122
0 0
.428571
The last 6 digits repeat forever.
.43125
This expansion terminates.
.113
The last 2 digits repeat forever.
.4344262295081967213114754098360655737704918032786
885245901639
The last 60 digits repeat forever.

来源(Source)

1994年北美中东部地区