思路与算法

以斐波那契转移矩阵Q观察Q^60≡I(mod10)。若Q^P≡I(mod10^k)，则(Q^P)^10≡I(mod10^(k+1))，所以60×10^(k-1)始终是合法周期，无需它最小。先枚举0..59中F与a模10一致的下标，逐层将每个候选扩成x+jP，j=0..9，用快速倍增模当前10次幂计算并筛选，直到10^13。无候选输出-1，否则最小候选即首次出现。

正确性说明

合法周期保证任何更大层周期内的下标唯一写作旧余数x加jP。能在高层匹配的下标在低层也匹配，因此不会被提前删掉；完整枚举全部十个提升保证无遗漏。快速倍增由F(2n)=F(n)(2F(n+1)-F(n))与F(2n+1)=F(n)^2+F(n+1)^2精确求值。最终所有下标按周期重复，最小代表就是第一次出现。

复杂度

初始60次计算；设各层候选数为Ck，总时间O(60log60+Σ10Ck logPk)，Pk=60×10^(k-1)，空间O(max Ck+logP13)。逐层向量初始化和全部候选均计入，不把候选数量假设为常数。

易错点

a=0首次下标0；a=1首次1而非2。模10^13的平方可达10^26，快速倍增使用128位中间乘积；周期6×10^13仍在64位范围。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
pair<ull, ull> fib(ull n, ull m) {
    if (!n)
        return {0, 1};
    auto q = fib(n / 2, m);
    ull a = q.first, b = q.second;
    ull c = (__uint128_t)a * ((2 * b % m + m - a) % m) % m,
        d = ((__uint128_t)a * a + (__uint128_t)b * b) % m;
    return n % 2 ? make_pair(d, (c + d) % m) : make_pair(c, d);
}
int main() {
    ull a;
    cin >> a;
    vector<ull> v;
    for (ull i = 0; i < 60; i++)
        if (fib(i, 10).first == a % 10)
            v.push_back(i);
    ull period = 60, mod = 10;
    for (int k = 2; k <= 13; k++) {
        mod *= 10;
        vector<ull> w;
        for (ull x : v)
            for (ull j = 0; j < 10; j++) {
                ull y = x + j * period;
                if (fib(y, mod).first == a % mod)
                    w.push_back(y);
            }
        v.swap(w);
        period *= 10;
    }
    if (v.empty())
        cout << -1 << '\n';
    else
        cout << *min_element(v.begin(), v.end()) << '\n';
}