UVa 202 Repeating Decimals（模拟+哈希）

原题地址

https://vjudge.net/problem/UVA-202

给出两个数n,m，0<=n,m<=3000，输出n/m的循环小数表示以及循环节长度。

解题思路

本题是《算法竞赛入门经典》的习题3-7，思路容易想到，实现起来有些细节和边界需要考虑。

不难想到，小数点后循环节的产生是因为计算时的某个余数重复出现，这之后的计算会重复上一次这个余数出现时直到当前位置的结果。因此关键在于找到这个重复出现的余数和它第一次出现的位置。

用res数组存放商的计算结果，dup[i]表示以余数i为计算来源的循环节的开始位置，即该余数i出现时的下一个要得到商的位置，初始化为0。while循环中模拟小学时候的除法，更新当前cnt位置的商的同时，判断计算结果的余数在之前是否出现过（dup[num]是否不为0）。当出现了循环节的时候，跳出循环，并以dup[num]~cnt-1间的数为所求循环节需要注意的是余数为0和分子本身为0的情况，他们的循环节都为1！！由于鸽笼原理， while循环一定会在分母值的次数内结束，其中必定会出现某个余数。 ps：测试用例要好好研究，非常有利于修正边缘情况的代码。最好每个都手动模拟一下，尤其联系dup[i]的意义观察下标的变化。

AC代码

#include <iostream> #include <stdio.h> #include <cstring> using namespace std; int main() { int num, deno; //num分子，deno分母 int res[3005], dup[3005]; //res存放计算结果，dup[i]表示余数i出现位置的下一个 while (cin >> num >> deno) { int ori_num = num; //记录原始num memset(res, 0, sizeof(res)); memset(dup, 0, sizeof(dup)); //清零 int cnt = 0; //当前需要产生商的位置 res[cnt++] = num/deno; //小数点前 num %= deno; while (dup[num] == 0 && num) //如果该余数曾经出现过，或者已经运算出0（循环一定在deno次内结束） { dup[num] = cnt; //该余数num即将产生第cnt个位置的商 res[cnt++] = num*10/deno; //产生商 num = num*10