题解 P7325 【[WC2021] 斐波那契】
Tiw_Air_OAO
2021-02-07 19:08:39
分享一个（自认为）比较简单的做法：
---
先特判 $a = 0$ 与 $b = 0$ 的情况。
定义 $f_n$ 为第 $n$ 个斐波那契数（这里取 $f_0 = 0, f_1 = 1$），则题目等价于 $af_{n-1} + bf_n = 0\bmod m$。
> 关于这一点，可以考虑 “转移矩阵中的值总可以写成斐波那契数”，那么第 $n$ 项即 $af_{n-1} + bf_n = 0\bmod m$。
---
一个自然的想法是变成 $-\frac{a}{b}=\frac{f_n}{f_{n-1}} \bmod m$，然而由于 $m$ 可以是合数，所以不一定互质。
考虑移项，并给 $a, b, m$ 同时除掉 $\gcd(a, b, m)$，得到：
$$
a'f_{n-1} = b'f_n \bmod m'(\gcd(a',b',m')=1)
$$
注意此时 $\gcd(a', m')$ 仍可以 $ > 1$。
由于 $\gcd(f_{n-1}, f_n) = 1$，此时应有 $\gcd(f_n, m') = \gcd(a',m') = p$ 以及 $\gcd(f_{n-1},m') = \gcd(b',m') = q$。
且此时等式两边以及模数同除 $pq$ 即可实现互质。
那么在 $m'$ 处塞个三元组 $(p,q,\frac{f_n}{f_{n-1}}\bmod \frac{m'}{pq})$，用 `std::map` 或 hash 维护，之后直接查询即可。
----
斐波那契数的循环节是 $O(n)$ 的（可以百度得到更进一步的分析）。
那么该算法预处理的复杂度为 $O(\sigma(m)\times \log m)$，其中 $\sigma(m)$ 是因子和，查询的复杂度是 $O(n\log m)$。
---
我的代码实现用的是 `std::map`，因此跑得比较慢。如果用 hash 可能会快一点。
```cpp
#include <bits/stdc++.h>
const int N = 200000;
int gcd(int x, int y) {return (y == 0) ? x : gcd(y, x % y);}
void exgcd(int a, int b, int &x, int &y) {
if( a == 1 ) {x = 1, y = 0;}
else exgcd(b, a % b, y, x), y -= a / b * x;
}
int inv(int a, int m) {
int x, y; exgcd(a, m, x, y);
return (x % m + m) % m;
}
struct node{
int x, y, z;
friend bool operator < (const node &a, const node &b) {
return (a.x == b.x) ? ((a.y == b.y) ? (a.z < b.z) : (a.y < b.y)) : (a.x < b.x);
}
};
int m; std::map<node, int>mp[N + 5];
void init() {
for(int i=2;i<=m;i++) if( m % i == 0 ) {
int x = 1, y = 0;
for(int j=0;;j++) {
if( x && y ) {
int d1 = gcd(i, x), d2 = gcd(i, y), m1 = i / d1 / d2;
int k = (int)(1ll * (y / d2) * inv((x / d1), m1) % m1);
if( !mp[i].count((node){k, d1, d2}) ) mp[i][(node){k, d1, d2}] = j;
}
int x1 = x; x = y, y = (x1 + y) % i;
if( x == 1 && y == 0 ) break;
}
}
}
int main() {
// freopen("fib.in", "r", stdin);
// freopen("fib.out", "w", stdout);
int n; scanf("%d%d", &n, &m), init();
for(int i=1,a,b;i<=n;i++) {
scanf("%d%d", &a, &b), b = (m - b) % m;
if( a == 0 ) {puts("0"); continue;}
if( b == 0 ) {puts("1"); continue;}
int d = gcd(gcd(a, b), m), m1 = m / d; a /= d, b /= d;
int p = gcd(a, m1), q = gcd(b, m1), m2 = m1 / p / q; a /= p, b /= q;
int k = (int)(1ll * a * inv(b, m2) % m2);
if( mp[m1].count((node){k, q, p}) ) printf("%d\n", mp[m1][(node){k, q, p}]);
else printf("-1\n");
}
}
```