USACO/fracdec

来自NOCOW

[编辑] 分析

（官方题解译 by 逆铭）
记得长除法吗？我们知道只有当出现了曾经出现过的余数时，小数部分才会出现重复。重复的部分就是自从我们上次见到同样的余数之后计算出的部分。
我们先读入并打印整数部分。接下来，我们对剩下的真分数部分进行长除直到我们发现了重复的余数或余数变为0。如果我们发现了重复的余数，即出现了循环节，就分别恰当地打印重复的部分和不重复的部分。如果余数变为0，即已经除尽，就打印整个小数部分。如果小数位根本没有被生成，那么打印一个0就是正确答案了。（此方法源码见：参考代码-> C/C++ -> 官方源码1）

下面是另一个更加优美的解法，来自Anatoly Preygel。
计算循环开始前的小数位数，这样你甚至无需保存各个小数位和余数，程序的空间花费将大幅减小，而运行速度也能有所提高。我们知道2和5的幂是仅有的两种不导致循环的数，因此要找到循环前的各数位，我们只需分别找到分子分母中包含的因子2和5个数的差，再取两者的最大值（详见代码片段）。然后我们仅使用第一个余数，在计算时输出各个数位即可（此方法源码见：参考代码-> C/C++ -> 官方源码2）（PASCAL见lsylsy21）。

我们知道，a/b的每位运算所得的余数只可能是0..b-1，如果在某处出现一个余数之前曾经出现过（在小数位上），那么可以肯定此时从该处到上次用出现这个这个商之间存在循环节。

用m记录每种余数是否曾经出现过，ss记录余数第一次出现的位置，如果余数为0就是整除，否则就找到循环节，输出

实际上,后面的小数内容完全取决于试除这一位时的商和余数.

另外,注意输出格式.

楼上更正一个细节，余数为0时就是除尽