自动搬运

查看原文

来自洛谷，原作者为

	metaphysis 故不积跬步，无以至千里；不积小流，无以成江海。——《荀子·劝学篇》

搬运于2025-08-24 22:12:11，当前版本为作者最后更新于2020-10-01 22:47:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解决本题需要一定的数论知识，核心是以下结论：给定一个整数 $m$，斐波那契数列 $F_n$ 模 $m$ 具有最小循环节。例如当 $m=2$ 时，$F_n$ 模 $2$ 的值为：

容易得知，当 $m=2$ 时，最小循环节长度为 $3$。

对于本题，有相关的两个结论：

（1）给定正整数 $m$，将 $m$ 进行素因子分解：

其中 $p_i$ 为素数，令 $c_i$ 表示 $F_n$ 模 ${p_i^{k_i}}$ 的最小循环节长度，$C$ 是 $F_n$ 模 $m$ 的最小循环节长度，则有

其中 $\operatorname{lcm}$ 表示最小公倍数。

（证明参见：Charles W. Campbell II, The Period of the Fibonacci Sequence Modulo j, 2007）

（2）若 $p$ 为素数，$F_n$ 模 $p^m$ 的最小循环节长度为 $G(p)×p^{m-1}$，其中 $G(p)$ 表示 $F_n$ 模 $p$ 的最小循环节长度。

通过枚举斐波那契数列可以容易得到：

再结合上述两个结论，有：

对于本题来说，由于给定的 $S$ 的最大长度不超过 $18$ 位，如果给定的 $k$ 存在，则有 $0<=k<=6×10^{18}$。

显然通过朴素的计算 $F_n$，然后比对末尾若干位的方法不可行，因为 $k$ 可能很大（参见：高精度加法这部分有问题，谁看一下？）。

一种可行的方法是使用回溯法，从低位到高位逐位枚举 $k$ 的各个数位上的数值，以期发现符合要求的 $k$。初看该方法似乎不可行，因为每个数位有 $0-9$ 这 $10$ 种可能，总的可能性最大为 $10^{18}$，但由于是逐位枚举，对于每个数位来说，符合之前及当前数位模结果的数字数量是非常少的，因此可以很快得到结果。在枚举的过程中需要充分利用结论 $G(10^m)=6×10^m$ 以便加快搜索速度，即按照 $10$ 的幂的最小循环节逐次累加。

举个例子，如果给定输入：

12345

个位是 $5$，由于 $F_n$ 模 $10$ 的最小循环节为 $60$，则从 $0$ 枚举到 $60$，确定一个 $k$，使得 $F_k$ 模 $10$ 的末位是 $5$，容易知道满足要求的最小 $k=5$，即 $F_5=5$，则当 $k=60×i+5(0<=i)$ 时，能够保证 $F_k$ 的末位是 $5$；接着确定十位，由于给定的 $S$ 十位为 $4$，则逐次枚举 $k=60×i+5(0<=i<=9)$，使得 $F_k$ 模 $100$ 为 $45$，得到 $k=245$ 时，$F_{245}$ 模 $100$ 为 $45$；接着确定百位，由于给定的 $S$ 百位为 $3$，逐次枚举 $k=600×i+245(0<=i<=9)$，使得 $F_k$ 模 $1000$ 为 $345$，得到 $k=1345$ 时，$F_{1345}$ 模 $1000$ 为 $345$；...，依此类推，最终可得 $k=149845$（注意，中间结果仅为示例，实际可能并不符合）。

以下是参考解题方案（编码未优化，加 $O2$ 优化 $Accepted$）：

// Fibonacci
// Luogu ID: 5580
// Verdict: Accepted
// Submission Date: 2020-10-01
// UVa Run Time: 2.80s

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

int found = 0, K;
ULL R, MODULO[20] = {0}, POW[20], CYCLE_OF_TEN[20];

struct matrix
{
    ULL cell[2][2];
    matrix(ULL a = 0, ULL b = 0, ULL c = 0, ULL d = 0)
    {
        cell[0][0] = a, cell[0][1] = b, cell[1][0] = c, cell[1][1] = d;
    }
} one(1, 1, 1, 0), zero(0, 0, 0, 0);

// 注意防止溢出。
ULL multiplyMod (ULL a, ULL b, ULL c)
{  
    ULL r = 0;  
    for ( ; b; b >>= 1)  
    {  
        if (b & 1)  
        {  
            r += a;
            if (r >= c) r -= c;  
        }  
        a <<= 1;
        if (a >= c) a -= c;  
    }  
    return r;  
}  

matrix multiply(const matrix &a, const matrix &b, ULL MOD)
{
    matrix r;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
            {
                r.cell[i][j] += multiplyMod(a.cell[i][k], b.cell[k][j], MOD);
                r.cell[i][j] %= MOD;
            }
    return r;
}

matrix matrixPow(ULL k, ULL MOD)
{
    if (k == 0) return zero;
    if (k == 1) return one;
    matrix r = matrixPow(k >> 1, MOD);
    r = multiply(r, r, MOD);
    if (k & 1) r = multiply(r, one, MOD);
    return r;
}

void dfs(int d, ULL k)
{
    if (found) return;
    if (d == K) { R = k; found = 1; return; }
    for (int i = 0; i < 10; i++)
    {
        // 当前末 d 位已经满足条件，寻找满足末 d+1 位的 k
        ULL nextk = (k + i * CYCLE_OF_TEN[d]) % CYCLE_OF_TEN[d + 1];
        // 检查 nextk 是否符合条件
        ULL fn = matrixPow(nextk, POW[d]).cell[0][0];
        if (fn == MODULO[d]) dfs(d + 1, nextk);
    }
}

int main(int argc, char *argv[])
{
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

    string S; cin >> S;
    if (stoll(S) == 0) { cout << "0\n"; return 0; }
    reverse(S.begin(), S.end());
    K = S.length();
    // MODULO[i] 表示 S 所对应的整数模 10^{i+1} 的结果
    // POW[i] 表示 10^{i+1}
    // CYCLE_OF_TEN[i] 表示 F_k 模 10^{i+1} 的最小循环节
    MODULO[0] = S[0] - '0', POW[0] = 10, CYCLE_OF_TEN[0] = 60;
    for (int i = 1; i <= K + 1; i++) POW[i] = POW[i - 1] * 10, CYCLE_OF_TEN[i] = CYCLE_OF_TEN[i - 1] * 10;
    for (int i = 1; i < K; i++) MODULO[i] = MODULO[i - 1] + (S[i] - '0') * POW[i - 1];
    // for (int i = 0; i < K; i++) cout << POW[i] << ' ' << MODULO[i] << '\n';
    // 对于个位数来说，其最小循环节为 60
    for (int k = 0; k < 60; k++) dfs(0, k);
    if (found) cout << (R + 1) << '\n';
    else cout << "NIE\n";

    return 0;
}