斐波那契数列

GitHub跳转原题关系图返回列表

先用短周期模 10^4 暴力收集候选下标,再借 pi(10^k) 每层扩大 10 倍的性质逐层扩散乘 10 并用倍增法验证,筛到 10^13 后取最小下标。

OJ: roj

题目 ID: 1808

难度:提高+/省选-

标签:数学数论矩阵二分

创建: 2026-10-08 04:32

更新: 2026-10-08 04:32

形式化题目

在模 101310^{13} 意义下定义斐波那契数列

F0≡0,F1≡1,Fn=Fn−1+Fn−2(mod1013)(n⩾2). F_0 \equiv 0, \quad F_1 \equiv 1, \quad F_n = F_{n-1} + F_{n-2} \pmod{10^{13}} \quad (n \geqslant 2).

给定 aa(0⩽a<10130 \leqslant a < 10^{13}),求最小的 n⩾0n \geqslant 0 使 Fn≡a(mod1013)F_n \equiv a \pmod{10^{13}}; 若不存在这样的 nn,输出 −1-1。

数据规模:0⩽a<10130 \leqslant a < 10^{13},时限 1000 ms,内存 512 MB。

直观做法是逐项递推并比对。问题在于数列在模 101310^{13} 下存在皮萨诺周期, 其长度等于 1.5×10131.5 \times 10^{13}:答案可能落在周期末尾,而"不存在"必须跑完整周期才能判定, 线性扫描的时间复杂度是 O(M)O(M),运算量达到 101310^{13} 次,无解情形必然超时。

正解

思路

关键观察:模数 101310^{13} 是 1010 的幂,于是"低位解"是"高位解"的必要条件。

若 Fn≡a(mod10k)F_n \equiv a \pmod{10^k},则对任意 j⩽kj \leqslant k 也有 Fn≡a(mod10j)F_n \equiv a \pmod{10^j}。 这让搜索可以分成两步:先在很小的模数下把所有候选下标找齐,再逐层向上过滤。

设皮萨诺周期为 π(m)\pi(m)。模 1010 的幂时有标准结论

π(2k)=3⋅2k−1 (k⩾3),π(5k)=20⋅5k−1,π(10k)=lcm⁡(π(2k),π(5k))=15⋅10k−1 (k⩾3). \pi(2^k) = 3 \cdot 2^{k-1}\ (k \geqslant 3), \qquad \pi(5^k) = 20 \cdot 5^{k-1}, \qquad \pi(10^k) = \operatorname{lcm}\bigl(\pi(2^k), \pi(5^k)\bigr) = 15 \cdot 10^{k-1}\ (k \geqslant 3).

周期每层正好扩大 1010 倍是本题的全部要害。它意味着:

若 nn 是模 10k10^k 的一个解,则 n mod π(10k−1)n \bmod \pi(10^{k-1}) 必是模 10k−110^{k-1} 的解; 反过来,模 10k10^k 的解一定落在 x+c⋅π(10k−1)x + c \cdot \pi(10^{k-1})(c=0,1,…,9c = 0, 1, \dots, 9)这 1010 个下标里, 其中 xx 是模 10k−110^{k-1} 的某个解。

于是搜索域被一层层压成"上一层候选数的 1010 倍",而每一层真正通过验证的候选极少。 取 k=4k = 4 作基底:π(104)=15000\pi(10^4) = 15000 很短,直接线性扫完一个周期就能拿到模 10410^4 的全部解。

流程:

  1. 递推一个 π(104)=15000\pi(10^4) = 15000 项周期,收集所有 Fn≡a(mod104)F_n \equiv a \pmod{10^4} 的下标,得到候选集 S4S_4。
  2. 对 k=5,6,…,13k = 5, 6, \dots, 13:把 Sk−1S_{k-1} 中每个 xx 扩散成 x+c⋅π(10k−1)x + c \cdot \pi(10^{k-1})(c=0…9c = 0 \dots 9), 用快速倍增法算 Fn mod 10kF_{n} \bmod 10^k,与 a mod 10ka \bmod 10^k 比对,通过者进入 SkS_k。
  3. S13S_{13} 即模 101310^{13} 一个周期内的全部解,取最小下标输出;若为空输出 −1-1。

为什么每层必须保留全部候选,不能只留最小的? 模 10k−110^{k-1} 下最小的解, 在模 10k10^k 下未必有合法的后继分支,而稍大一点的解可能才有。贪心剪枝会漏解。

为什么验证必须用快速倍增? 第 kk 层的下标可达 1.5×10k−11.5 \times 10^{k-1}, 线性递推到那里是 101310^{13} 次加法,不可接受;倍增法每次 O(log⁡n)O(\log n),共约 4444 次乘法。

a=0\boldsymbol{a = 0} 的处理。 F0=0F_0 = 0,00 的最早出现位置就是 00 本身, 而 n=π(1013)=1.5×1013n = \pi(10^{13}) = 1.5 \times 10^{13} 也是一个解。算法不特判,只要最后取最小值, 自然会选出 00;但正因为存在这个"尾部解",一旦代码把下标 00 弄丢或忘了取 min⁡\min,就会输出末尾的大下标。

溢出。 在模 101310^{13} 下做乘法时 Fk⋅Fk+1F_k \cdot F_{k+1} 最大可达 102610^{26}, 超过 64 位的 1.8×10191.8 \times 10^{19}。因此模乘必须用 unsigned __int128 承接中间结果再取模。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 04:32
# update_at: 2026-10-08 04:32

import sys

MOD13 = 10 ** 13      # 题目要求的模数
MOD4 = 10 ** 4        # 基底模数,取它是因为 pi(10^4) 很短且规律标准
PERIOD4 = 15000       # 皮萨诺周期 pi(10^k) = 15 * 10^(k-1)(k >= 3)


def fib_mod(n: int, mod: int) -> int:
    """快速倍增求 F_n mod mod(迭代处理 n 的二进制位,从最高位起)。"""
    fk, fk1 = 0, 1 % mod                       # 当前持有的 (F_k, F_{k+1})
    for bit in bin(n)[2:]:
        c = fk * ((2 * fk1 - fk) % mod) % mod  # F_{2k}   = F_k * (2F_{k+1} - F_k)
        d = (fk * fk + fk1 * fk1) % mod        # F_{2k+1} = F_k^2 + F_{k+1}^2
        fk, fk1 = (d, (c + d) % mod) if bit == '1' else (c, d)
    return fk


def solutions(a: int) -> list[int]:
    """逐层截断提升,返回模 10^13 下一个周期内所有满足 F_n ≡ a 的下标。"""
    cur: list[int] = []
    f0, f1 = 0, 1                              # 底层暴力枚举 pi(10^4) 项
    for n in range(PERIOD4):
        if f0 == a % MOD4:
            cur.append(n)
        f0, f1 = f1, (f0 + f1) % MOD4

    mod, period = MOD4, PERIOD4
    while cur and mod < MOD13:
        step, period, mod = period, period * 10, mod * 10   # pi 每层恰好扩大 10 倍
        target = a % mod                       # 只比较当前层的低位,不能用完整的 a
        nxt: list[int] = []
        for x in cur:
            for c in range(10):                # 新解必落在上一层的 x + c*step 上
                n = x + c * step
                if fib_mod(n, mod) == target:
                    nxt.append(n)
        cur = nxt
    return cur


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    a = next(data)
    print(min(solutions(a), default=-1))       # 无解时 default 给出 -1


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 04:32
 * update_at: 2026-10-08 04:32
 */
// 一本通 1808 《斐波那契数列》
// 题意:求最小的 n>=0 使 F_n ≡ a (mod 10^13),不存在输出 -1。
//
// 思路(逐层截断提升):
//   先取一个周期极短的基底模数 10^4(皮萨诺周期 pi(10^4)=15000),
//   暴力枚举一个周期,收集所有满足 F_n ≡ a (mod 10^4) 的下标作为候选集。
//   对 k>=3 有 pi(10^k)=15*10^(k-1),即周期随 k 每增 1 恰好扩大 10 倍。
//   于是"模 10^k 的解"必须落在"模 10^(k-1) 的某个解 r 加上 c*pi(10^(k-1))"
//   这 10 个类里(c=0..9),逐层过滤到 k=13,剩下的候选取最小下标即为答案。
//   每层判断用快速倍增求 F_n mod 10^k,O(log n) 一次。
//
// 溢出:模 10^13 时两数相乘可达 10^26,必须用 unsigned __int128 承接中间结果。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned __int128 u128;

const ll MOD13 = 10000000000000LL;  // 10^13
const ll MOD4 = 10000LL;            // 基底模数 10^4
const ll PERIOD4 = 15000LL;         // 皮萨诺周期 pi(10^4) = 1.5*10^4

ll a;                 // 待查询的值
vector<ll> cur, nxt;  // 候选下标集(逐层交替使用)

// 模 m 乘法:m 最大 10^13,乘积最大 10^26,用 128 位承接
ll mulmod(ll x, ll y, ll m) {
    return (ll)((u128)x * y % (u128)m);
}

// 快速倍增求 F_n mod m,返回 F_n;迭代处理 n 的二进制位
ll fib_mod(ll n, ll m) {
    ll fk = 0, fk1 = 1 % m;  // 当前 (F_k, F_{k+1}),初始 k=0
    for (int bit = 62; bit >= 0; bit--) {
        // (F_{2k}, F_{2k+1}) = (F_k*(2F_{k+1}-F_k), F_k^2 + F_{k+1}^2)
        ll c = mulmod(fk, ((2 * fk1 - fk) % m + m) % m, m);
        ll d = (mulmod(fk, fk, m) + mulmod(fk1, fk1, m)) % m;
        if ((n >> bit) & 1) {
            fk = d;
            fk1 = (c + d) % m;
        } else {
            fk = c;
            fk1 = d;
        }
    }
    return fk;
}

int main() {
    scanf("%lld", &a);

    // 第 4 层:暴力枚举一个模 10^4 的周期,收集全部候选下标
    ll f0 = 0, f1 = 1;
    for (ll n = 0; n < PERIOD4; n++) {
        if (f0 == a % MOD4) cur.push_back(n);
        ll t = (f0 + f1) % MOD4;
        f0 = f1;
        f1 = t;
    }

    // 第 5..13 层:每层候选只可能来自上一层的 x + c*period(c=0..9)
    ll mod = MOD4, period = PERIOD4;
    while (!cur.empty() && mod < MOD13) {
        ll step = period;  // 上一层的周期,也是本层的扩散步长
        period *= 10;      // pi(10^k) 随 k 每增 1 扩大 10 倍
        mod *= 10;
        nxt.clear();
        for (size_t i = 0; i < cur.size(); i++) {
            for (int c = 0; c < 10; c++) {
                ll n = cur[i] + (ll)c * step;  // n < 1.5*10^13,ll 足够
                if (fib_mod(n, mod) == a % mod) nxt.push_back(n);
            }
        }
        cur.swap(nxt);
    }

    if (cur.empty()) {
        printf("-1\n");
    } else {
        ll best = cur[0];
        for (size_t i = 1; i < cur.size(); i++)
            if (cur[i] < best) best = cur[i];
        printf("%lld\n", best);
    }
    return 0;
}

复杂度

  • 基底:1500015000 次加法,O(π(104))O(\pi(10^4))。
  • 提升:共 99 层,每层候选数在斐波那契数列的性质下始终很小(个位数级别), 每层每个候选扩散 1010 个分支,每次验证 O(log⁡n)O(\log n) 次矩阵式乘法(约 4444 次模乘)。 总运算量远小于 10510^5,常数级别。
  • 空间:只维护两个长度极短的候选列表,O(1)O(1)。

总结

  • 「101310^{13} 是 1010 的幂」把"横向全周期扫描"换成"纵向逐层过滤": 低模数的解一定是高模数解的前缀,于是每层只在上层解的 1010 倍扩张里找。
  • π(10k)=15⋅10k−1\pi(10^k) = 15 \cdot 10^{k-1}(k⩾3k \geqslant 3)保证扩张步长每层恰好乘 1010, 这正是"每层枚举 c=0…9c = 0 \dots 9"这一写法的依据。
  • 分支必须全部保留、验证必须用快速倍增、模乘必须用 128 位,是实现上的三个必守点。
  • 本题素材源(new_ROJ/problems/1808/)自带数据生成脚本 data.py,测试数据由脚本自造, 题面亦为重建版本,与出题人原始数据可能存在偏差;本文结论以仓库内 10 个数据点为准, 未声称与官方原题数据完全一致。