突然发现 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;
}
0 条评论