题目描述
单位分数指分子为 的分数
例如
这里括号表示循环节， 的循环节为
，长度为
在所有满足 的数中，求使得其倒数
的十进制表示中循环节最长的
。
思路
直接竖式除法模拟即可
代码
// 倒数的循环节
#include <cstdio>
#include <cstring>
int pos[1005];
int ans;
// 模拟竖式除法，获取循环节的长度
int getLen(int x) {
memset(pos, 0, sizeof(pos));
int r = 1, t = 0; // r 为余数，t为小数点后的数位
while (r) {
t += 1;
r = (r * 10) % x; // 这两步可理解为在余数后添一个 0 试除
if (pos[r]) return t - pos[r]; // 余数 r 之前出现过，则说明进入循环
pos[r] = t;
}
return 0;
}
int main() {
for (int i = 2; i < 1000; i++) {
int len = getLen(i);
if (len > ans) ans = len;
}
printf("%d\n", ans);
return 0;
}
