Project_Euler-26 题解

题目

思路

暴力枚举。

题目中已经给了一个范围：$d<1000$，我们可以尝试顺着这个思路往下走，遍历这1000个值，分别查看 $1/d$ 的值中有没有循环节，并看看他们有多长。

对于拿到的值 $d$ ，我们让它除1然后取余数。我们可以维护一个步数step，表示已经除了多少步，如果除尽了，说明没有循环节，直接返回 $-1$，对于没有除进的，我们维护一个标记数组range，在余数对应的下标数组中记录步数，如果在向后除的过程中，又遇到了相同的数，则将当前的step减去原来记录的step就可以求出循环节的长度了。

例如，某个数的余数是这样的：

$$123\mathrm{123123...}$$

我们假设除到1时，step为1，那么接下来如下表格所示：

num	1	2	3	1	2
step	1	2	3	4	5
range	1	2	3	-	-

表格中两个红色的实体执行减法。

代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>
#define MAX_N 1000

int poe[MAX_N];

int getlen(int x) {
    memset(poe, 0, sizeof(poe));
    // r代表当前的被除数，一开始为1，step的初始值其实并不重要，最终取的是差
    int r = 1, step = 1;
    while(r) {
    	// 对于每一个余数要记得先给他乘上10，这样不会出现小数，方便再取余数
        r *= 10;
        r %= x;
        step += 1;
        if (poe[r]) return step - poe[r];
        poe[r] = step;
    }
    return 0;
}

int main() {
    int d = 0, len = 0;
    for (int i = 2; i < MAX_N; i++) {
        int temp = getlen(i);
        if (temp <= len) continue;
        len = temp;
        d = i;
    }
    printf("len = %d, d = %d\n", len, d);
    return 0;
}