题解 P7325 【[WC2021] 斐波那契】

· · 题解

分享一个（自认为）比较简单的做法：

先特判 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 可能会快一点。

#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");
    }
}