欧拉计划 26

Reciprocal cycles

题目描述

单位分数指分子为 的分数
例如
这里括号表示循环节， 的循环节为 ，长度为

在所有满足 的数中，求使得其倒数 的十进制表示中循环节最长的 。

思路

直接竖式除法模拟即可

代码

// 倒数的循环节
#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;
}