题解：P7325 [WC2021] 斐波那契
Charllote_
·
·
题解
题解：P7325 [WC2021] 斐波那契
更好的阅读体验\
题目传送门
题意简述
有 F_0 = a，F_1 = b，F_i = (F_{i-1} + F_{i-2}) \bmod m（i \ge 2），求 \min\{p\} 使得 F_p = 0。
规定
F_n = \left\{\begin{aligned} 0 \space (n \le 1)\\1 \space (n=1) \\ F_{n-1}+F_{n-2} \space (n\ge 2) \end{aligned}\right.
题中序列为 G。
$a \perp b$ 为 $a$、$b$ 互质。
## 题目思路
首先容易发现原问题等价于求 $\min\{n\}$ 使得 $aF_{n-1}+bF_n\equiv 0\pmod m$。
> 证明：
>
> 当 $n = 2$ 时：$G_2 = G_0 + G_1 = b = (F_0a + F_1b) \bmod m$。
>
> 当 $n =3$ 时：$G_3 = G_1+ G_2 = a + b = (F_1a+F_2b) \bmod m$。
>
> 设当 $n \le i$ 时 $F_n = aF_{n-1}+bF_n$ 成立。
>
> 当 $n = i + 1$ 时：$G_{i + 1} = (G_i + G_{i - 1}) \bmod m = (aF_{i - 1} + bF_i+aF_{i - 2} + bF_{i - 1}) \bmod m = (aF_{i}+bF_{i-1})\bmod m$。
>
> 故 $aF_{n-1}+bF_n\equiv G_n\pmod m$。
为了解决原题，考虑把推导出一个形如 $B\equiv A\pmod m$（$A$ 为和 $a$、$b$、$m$ 有关的式子、$B$ 为和 $F$ 有关的式子）。
设 $d = (a, b, m)$、$a' = \frac{a}{d}$、$b'=\frac{b}{d}$、$m'=\frac{m}{d}$ 则 $a' F_{n-1}+b' F_n\equiv 0\pmod {m'}$。
> 证明：
>
> 若 $x \equiv y \pmod z$，设 $d=(x, z, y)$。
>
> $\because x\bmod z = (\frac{x}{d}\bmod z)d$，$y\bmod z = (\frac{y}{d}\bmod z)d$，$x \equiv y \pmod z$。
>
> $\therefore (\frac{x}{d}\bmod z)d \equiv (\frac{y}{d}\bmod z)d \pmod z$。
>
> $\therefore \frac{x}{d} \equiv \frac{y}{d} \pmod {\frac{z}{d}}$。
因为 $F_n \perp F_{n - 1}\space(1)$，所以 $(F_n,m')=(a',m')=p\space(2)$、$(F_{n-1},m')=(b',m')=q\space(2)$。
> $F_n \perp F_{n - 1}\space(1)$ 证明：
>
> 当 $n=2$ 时：$F_2 = 1, F_1=1,F_1 \perp F_2$。
>
> 当 $n=3$ 时：$F_3 = 2, F_2=1,F_3 \perp F_2$。
>
> 设当 $n\le i$ 时 $F_n \perp F_{n - 1}$ 成立。
>
> 当 $n = i + 1$ 时：
>
> 设 $d = (F_i,F_{i+1})$，则：$d \mid F_i$、$d\mid F_{i + 1}$。
>
> $\because F_n = F_{n-1}+F_{n-2}$。
>
> $\therefore d\mid (F_{i+1}-F_i)=F_{i-1}$。
>
> $\therefore d=(F_{i-1},F_i)=1\Rightarrow F_{i + 1} \perp F_i$。
>
> 故 $F_n \perp F_{n - 1}$。
> $(F_n,m')=(a',m')=p\space(2)$、$(F_{n-1},m')=(b',m')=q\space(2)$ 证明。
>
> 设 $p=(F_n,m')$，则 $p\mid F_n$、$p\mid F_{n - 1}$。
>
> 又 $\because a' F_{n-1}+b' F_n\equiv 0\pmod {m'} \Rightarrow a' F_{n-1}=km-b' F_n$。
>
> $\therefore p\mid a'F_{n-1}$。
>
> 又 $\because F_n \perp F_{n - 1}$，$p \perp F_n$。
>
> $\therefore p\mid a'$。
>
> 反之，设 $p'=(a',m')$ 可得 $p'\mid F_n$。
>
> 综上 $(F_n,m')=(a',m')=p$，同理 $(F_{n-1},m')=(b',m')=q$。
$a' F_{n-1}+b' F_n\equiv 0\pmod {m'}$ 两边同时除以 $pq$ 得 $\frac{a'}{pq}F_{n-1}+\frac{b'}{pq} F_n\equiv 0\pmod {\frac{m'}{pq}}$。易证加号两边互质，移项可得 $-\frac{b'}{a'}\equiv \frac{F_{n-1}}{F_n}\pmod {\frac{m'}{pq}}$。
由于斐波那契数列在模 $m$ 意义下是有循环节的，我们可以先预处理，对于每个 $m'$，计算 $\frac{F_{n-1}}{F_n}\bmod \frac{m'}{pq}$、$p$、$q$，并存储三元组 $(p,q,\frac{Fn−1}{Fn} \bmod \frac{m′}{pq})$。对于每组询问的 $a$、$b$，计算 $d$，并得到 $a′$、$b′$、$m′$。计算 $p$、$q$、$-\frac{b'}{a'}\bmod \frac{m'}{pq}$，在存储的三元组中查找是否存在对应的项。如果存在，则找到最小的 $n$ 使得满足条件，如果不存在，则输出 $−1$。
## AC code
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200000;
using PPIII = pair<pair<int, int>, int>;
int n, m, a, b;
map<PPIII, int> ck[N + 5];
void exgcd(int a, int b, int &x, int &y) {
if (a == 1) {
x = 1;
y = 0;
return ;
}
exgcd(b, a % b, y, x);
y -= a / b * x;
}
//解方程 ax + by = 0
int inv(int x, int m) {
int n, temp;
exgcd(x, m, n, temp);
return (n % m + m) % m;
}
//解同余方程求逆元
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 2; i <= m; i ++ )
if (m % i == 0) { // 枚举 m'
int x = 1, y = 0, s = 0;
while (true) { // 枚举斐波那契数列
if (x != 0 && y != 0) {
int dx = __gcd(x, i), dy = __gcd(y, i);
int mp = i / dx / dy;
int t = ((y / dy) * inv((x / dx), mp) % mp + mp) % mp;
// 存储
if (!ck[i].count({{dx, dy}, t}))
ck[i][{{dx, dy}, t}] = s;
// 保存
}
int t = x;
x = y;
y = (t + y) % i;
// 计算下一对
if (x == 1 && y == 0) break;
// 循环节
s ++ ;
}
}
while(n -- ) {
cin >> a >> b;
b = (m - b) % m;
if (a == 0) {
cout << "0\n";
continue;
}
if(b == 0) {
cout << "1\n";
continue;
}
// 特殊判断
int d = __gcd(__gcd(a, b), m), mp = m / d;
a /= d; b /= d;
int p = __gcd(a, mp), q = __gcd(b, mp), mpp = mp / p / q;
a /= p, b /= q;
int k = (a * inv(b, mpp) % mpp + mpp) % mpp;
// 查询
if (ck[mp].count({{q, p}, k}))
cout << ck[mp][{{q, p}, k}] << '\n';
else
cout << "-1\n";
// 查询答案
}
return 0;
}
```