【题解】WC2021 斐波那契 数论 — Qiuly

突然发现 WC2021 到现在还没做 ..

考虑我们要求的应该是最小的 $i$ 使得满足 $f_{i-1}a\equiv f_{i}b\pmod {p}$ 。

即满足 $p|f_{i-1}a-f_ib$，因此 $\frac{p}{\gcd(p,a,b)}|f_{i-1}\frac{a}{\gcd(p,a,b))}-f_i\frac{b}{\gcd (p,a,b)}$，记 $g=\gcd(p,a,b)$ 即有 $\frac{p}{g}|f_{i-1}\frac{a}{p}-f_i\frac{b}{g}$ 。

此时观察 $f_{i-1}\frac{a}{g}\equiv f_i\frac{b}{g}\pmod{\frac{p}{g}}$，显然有 $f_i\perp f_{i-1}$ 。记 $g’=\gcd(\frac{a}{p},\frac{b}{p})$ 存在 $g’\perp \frac{p}{g}$ ，此时令 $a’=\frac{a}{gg’},b’=\frac{b}{gg’},p’=\frac{p}{g}$ 。要解决的新问题变为 $f_{i-1}a’\equiv f_{i}b’\pmod {p’}$，同时有 $a’\perp b’$ 。

此时考虑令 $g_a=\gcd (a’,p’)$，即 $f_{i-1}\frac{a’}{g_a}g_a-f_{i}b=k_pp’\frac{p’}{g_a}g_a$，因此 $\left(f_{i-1}\frac{a’}{g_a}-k_pp’\frac{p’}{g_a}\right)g_a=f_{i}b$，这说明 $g_a|f_ib$，即 $g_a|f_i$ 。

同理令 $g_b=\gcd(b’,p’)$，可证 $g_{b}|f_{i-1}$ 。因此我们需要解决 $\frac{f_{i-1}}{g_{b}}\frac{a’}{g_a}\equiv \frac{f_i}{g_a}\frac{b’}{g_b}\pmod{\frac{p’}{g_ag_b}}$，此时显然有 $\frac{b’}{g_b}\perp\frac{p’}{g_ag_b}$。对于证明 $\frac{f_{i-1}}{g_b}\perp \frac{p’}{g_ag_b}$ 考虑反证，若存在 $\gcd(\frac{f_{i-1}}{g_b},\frac{p’}{g_ag_b})=d$ 且 $d>1$，即有 $d|\frac{f_i}{g_a}\frac{b’}{g_b}$，也即 $d|\frac{b’}{g_b}$，这与 $\frac{b’}{g_b}\perp\frac{p’}{g_ag_b}$ 相矛盾。

因此上述两者都存在模 $\frac{p’}{g_ag_b}$逆元，我们需要处理的问题变成了 $\frac{a’}{g_a}\left(\frac{b’}{g_b}\right)^{-1}\equiv \frac{f_i}{g_a}\left(\frac{f_{i-1}}{g_b}\right)^{-1}\pmod{\frac{p’}{g_ag_b}}$ 。此时可以发现，因为存在 $g_a\perp f_{i-1}$，因此 $\gcd(f_{i-1},p’)=g_b$ 和 $g_a$ 无关，同理可得 $\gcd(f_{i},p)=g_a$ 。即 $\gcd(f_{i-1},p’)=\gcd(b’,p’)$，同理可得 $\gcd(f_{i},p’)=\gcd (a’,p’)$ 。

考虑到 $p’ |m$，而模 $m$ 意义下斐波那契序列的循环节长度为 $O(m)$，$m$ 的因子和数量级为 $O(m\log\log m)$，考虑用 hash 表预处理所有可能的 $(\gcd(f_i,p’),\gcd(f_{i-1},p’),\frac{f_i}{g_a}\left(\frac{f_{i-1}}{g_b}\right)^{-1}\bmod \frac{p’}{g_ag_b})$ 即可。

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) fprintf (stderr, __VA_ARGS__)

#define lep(i, l, r) for (int i = (l), i##_end = (r); i <= i##_end; ++ i)
#define rep(i, r, l) for (int i = (r), i##_end = (l); i >= i##_end; -- i)

char __c; bool __f; template <class T> inline void IN (T & x) {
    __f = 0, x = 0; while (__c = getchar (), ! isdigit (__c)) if (__c == '-') __f = 1;
    while (isdigit (__c)) x = x * 10 + __c - '0', __c = getchar (); if (__f) x = -x;
}

template <class T> inline void chkmin (T & x, T y) { if (x > y) x = y; }
template <class T> inline void chkmax (T & x, T y) { if (x < y) x = y; }

struct barrett {
    int p; __int128 w;
    inline void init (int mod) { p = mod, w = - 1ull / p; }
    inline int reduce (ll x) {
        ll t = x - (w * x >> 64) * p;
        return t >= p ? t - p : t;  
    }
} __mod;

inline int mul (int x, int y) { return __mod.reduce (1ll * x * y); }

int gcd (int x, int y) { return y ? gcd (y, x % y) : x; }
void exgcd (int x, int y, int &a, int &b) {
    if (! y) return a = 1, b = 0, void ();
    return exgcd (y, x % y, b, a), b -= (x / y) * a, void ();
}
inline int inv (int x) {
    int a, b; exgcd (x, __mod.p, a, b);
    return __mod.reduce (__mod.reduce (a) + __mod.p);
}

const int N = 1e5 + 5;
const ll B2 = 1e12, B1 = 1e6;

int m, a, b;
unordered_map <ll, int> mp[N];

inline ll zip (int ga, int gb, int _inv) { return B2 * ga + B1 * gb + _inv; }

inline void init (const int L = N - 5) {
    lep (p, 2, m) if ((m % p) == 0) {
        int f0 = 1, f1 = 1;

        for (int i = 2; ; ++ i) {
            int ga = gcd (f1, p);
            int gb = gcd (f0, p);

            __mod.init (p / ga / gb);
            ll key = zip (ga, gb, mul (f1 / ga, inv (f0 / gb)));
            if (! mp[p].count (key)) mp[p][key] = i;

            int f2 = (f0 + f1) % p;
            if (f0 = f1, f1 = f2, f0 == 1 && f1 == 1) break ;
        }
    }
}
signed main () {
    int T;
    IN (T), IN (m), init ();

    while (T -- ) {
        int p = m; __mod.init (p);

        IN (a), a = __mod.reduce (a); 
        IN (b), b = __mod.reduce (p - __mod.reduce (b));
        if (a == 0) { puts ("0"); continue ; }
        if (b == 0) { puts ("1"); continue ; }

        int g1 = gcd (a, b), g0 = gcd (g1, p);
        a = a / g1, b = b / g1, p = p / g0;

        int ga = gcd (a, p);
        int gb = gcd (b, p);

        __mod.init (p / ga / gb);
        ll key = zip (ga, gb, mul (a / ga, inv (b / gb)));

        if (mp[p].count (key)) printf ("%d\n", mp[p][key]);
        else puts ("-1");
    }
    return 0;
}