题面

传送门

广为人知的斐波拉契数列 fib(n)\mathrm{fib}(n) 是这么计算的

fib(n) = {0,n=01,n=1fib(n1)+fib(n2),n>1fib(n)\ =\ \left\{\begin{array}{lc}0,&n=0\\1,&n=1\\fib(n-1)+fib(n-2),&n>1\end{array}\right.

也就是 0,1,1,2,3,5,8,130, 1, 1, 2, 3, 5, 8, 13 \cdots,每一项都是前两项之和。

小 F 发现,如果把斐波拉契数列的每一项对任意大于 11 的正整数 MM 取模的时候,数列都会产生循环。

当然,小 F 很快就明白了,因为 (fib(n1)modM\mathrm{fib}(n - 1) \bmod M) 和 (fib(n2)modM)\mathrm{fib}(n - 2) \bmod M) 最多只有 M2M ^ 2 种取值,所以在 M2M ^ 2 次计算后一定出现过循环。

甚至更一般地,我们可以证明,无论取什么模数 MM,最终模 MM 下的斐波拉契数列都会是 0,1,,0,1,0, 1, \cdots, 0, 1, \cdots

现在,给你一个模数 MM,请你求出最小的 n>0n > 0,使得 fib(n)modM=0,fib(n+1)modM=1\mathrm{fib}(n) \bmod M = 0, \mathrm{fib}(n + 1) \bmod M = 1

思路

暴力+优化 = AC

代码

#include <bits/stdc++.h>

using namespace std;

long long a[10000000];

long long dfib(long long x, long long m) {
    if (a[x] != -1) {
        return a[x];
    }
    if (x == 0) {
        a[x] = 0 % m;
        return 0;
    }
    if (x == 1) {
        a[x] = 1 % m;
        return 1;
    }
    a[x] = (dfib(x - 1, m) + dfib(x - 2, m)) % m;
    return a[x];
}

int main() {
    long long m;
    memset(a, 0xff, sizeof(a));
    cin >> m;
    for (int i = 2; i < m * m; i++) {
        if (dfib(i, m) == 0 && dfib(i + 1, m) == 1) {
            cout << i;
            break;
        }
    }
    return 0;
}