先用短周期模 10^4 暴力收集候选下标,再借 pi(10^k) 每层扩大 10 倍的性质逐层扩散乘 10 并用倍增法验证,筛到 10^13 后取最小下标。
OJ: roj
题目 ID: 1808
难度:提高+/省选-
标签:数学数论矩阵二分
创建: 2026-10-08 04:32
更新: 2026-10-08 04:32
形式化题目
在模
给定
数据规模:
直观做法是逐项递推并比对。问题在于数列在模
正解
思路
关键观察:模数
若
设皮萨诺周期为
周期每层正好扩大
若
是模 的一个解,则 必是模 的解; 反过来,模 的解一定落在 ( )这 个下标里, 其中 是模 的某个解。
于是搜索域被一层层压成"上一层候选数的
流程:
- 递推一个
项周期,收集所有 的下标,得到候选集 。 - 对
:把 中每个 扩散成 ( ), 用快速倍增法算 ,与 比对,通过者进入 。 即模 一个周期内的全部解,取最小下标输出;若为空输出 。
为什么每层必须保留全部候选,不能只留最小的? 模
为什么验证必须用快速倍增? 第
溢出。 在模 unsigned __int128 承接中间结果再取模。
代码
#!/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()/**
* 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;
}复杂度
- 基底:
次加法, 。 - 提升:共
层,每层候选数在斐波那契数列的性质下始终很小(个位数级别), 每层每个候选扩散 个分支,每次验证 次矩阵式乘法(约 次模乘)。 总运算量远小于 ,常数级别。 - 空间:只维护两个长度极短的候选列表,
。
总结
- 「
是 的幂」把"横向全周期扫描"换成"纵向逐层过滤": 低模数的解一定是高模数解的前缀,于是每层只在上层解的 倍扩张里找。 ( )保证扩张步长每层恰好乘 , 这正是"每层枚举 "这一写法的依据。 - 分支必须全部保留、验证必须用快速倍增、模乘必须用 128 位,是实现上的三个必守点。
- 本题素材源(
new_ROJ/problems/1808/)自带数据生成脚本data.py,测试数据由脚本自造, 题面亦为重建版本,与出题人原始数据可能存在偏差;本文结论以仓库内 10 个数据点为准, 未声称与官方原题数据完全一致。