p7325

首先通过分析 $a,b$ 各自贡献系数容易得到 $F_n=af_{n-1}+bf_n$（$n=0$ 特判掉呗），其中 $f$ 是斐波那契数列。一开始还 GF 推半天推出了一个人不人鬼不鬼的玩意（ 然后就是 $af_{n-1}+bf_n\equiv0\pmod m$。令 $b\gets-b$，有 $af_{n-1}\equiv bf_n\pmod m$。到这一步，如果 $m$ 是质数容易想到变量分离，得到 $\dfrac ab\equiv\dfrac{f_n}{f_{n-1}}\pmod m$（$0$ 不 $0$ 的就特判吧），而我们熟知斐波那契数列在模意义下是纯循环的并且循环节不超过 $6m$，所以 $\dfrac{f_n}{f_{n-1}}$ 不同的只有 $\mathrm O(m)$，存起来放到 `map` 里查询就可以了。可惜 $m$ 不一定是质数/qd 接下来就需要用到模合数的移项技巧了，其核心是一个等价变换：若 $d\mid a,b,m$，则 $a\equiv b\pmod m$ 等价于 $\dfrac ad\equiv\dfrac bd\pmod{\dfrac md}$。 先把 $a,b,m$ 约掉 $d=\gcd(a,b,m)$，设 $a'=\dfrac ad,b'=\dfrac bd,m'=\dfrac md$，则原方程等价于 $a'f_{n-1}\equiv b'f_n\pmod{m'}$。此时我们想把 $b'$ 移到左边，可此时 $b'$ 与 $m'$ 不一定互质。考虑 $d'=\gcd(b',m')$，则 RHS 一定是 $d'$ 的倍数，LHS 便也必须是。而由于既约性，$a'\perp d'$，所以只能是 $d'\mid f_{n-1}$。于是便可三边再约掉 $d'$，设 $b''=\dfrac{b'}{d'},m''=\dfrac{m'}{d'}$，则 $a'\dfrac{f_{n-1}}{d'}\equiv b''f_n\pmod{m''}$。此时便可把 $b''$ 移过来，得 $a'(b'')^{-1}\dfrac{f_{n-1}}{d'}\equiv f_n\pmod{m''}$。 现在再想把 $\dfrac{f_{n-1}}{d'}$ 移到右边（这个 dfrac 是一个整体不能拆的/qd）。再来重复上面的剧本：先三边都约掉 $\dfrac{f_{n-1}}{d'},f_n,m''$ 的 gcd。而我们熟知 $f_{n-1}\perp f_n$，所以这个 gcd 一定是 $1$，此处不用约！考察 $d''=\gcd\!\left(\dfrac{f_{n-1}}{d'},m''\right)$，RHS 必须是 $d''$ 的倍数，而一方面有既约性，另一方面 RHS 除了 $f_n$ 没有别人帮它承担整除性了，所以此处必须要有 $d''=1$。那么直接就可以移了：$a'(b'')^{-1}\equiv f_n\left(\dfrac{f_{n-1}}{d'}\right)^{-1}\pmod{m''}$。 现在考虑预处理装 `map`。注意到最终的式子是与 $d'$ 与 $m''$ 相关的，在预处理的时候也应当枚举这两者，同时满足 $d'\mid f_{n-1}$ 且 $d''=1$。而 $(d',m'')$ 对数有 $(\mathrm d*1)(m)$ 个，每对还要 $\mathrm O(m)$ 枚举，无疑是爆炸。不过观察到 $d''=1$ 即 $\dfrac{f_{n-1}}{d'}\perp m''=\dfrac{m'}{d'}$，即 $d'=\gcd(f_{n-1},m')$，那么只要枚举 $m'$，$d'$ 就确定了！于是枚举 $m'$ 的复杂度是 $\mathrm d(m)$ 的话，大约 100 左右，再配上 $\mathrm O(m)$ 枚举，感觉差不多。 --- 事实上，枚举到 $m'$ 时只需要关心模 $m'$ 意义下的斐波那契数列，所以此时枚举其实是 $\mathrm O(m')$，最终复杂度显然就是 $\mathrm O(\sigma(m))$（再乘以一个 `map` 的 log）。这是个什么量级呢？我自己估计了一下，可能结果不是很好（ 设 $m$ 分解质因数为 $\prod p_i^{\alpha_i}$，则 $$ \begin{aligned} \sigma(m)&=\prod\dfrac{p_i^{\alpha_i+1}-1}{p_i-1}\\ &\leq\prod\dfrac{p_i^{\alpha_i+1}}{p_i-1}\\ &\leq m\prod\!\left(1+\dfrac{1}{p_i-1}\right)\\ &\leq m\prod\exp\dfrac1{p_i-1}\\ &=m\exp\sum\dfrac1{p_i-1} \end{aligned} $$ 以上用到了不等式 $1+x\leq \mathrm e^x$（还是最近学 Pollard-Rho 学会的）。下面估计一下 $\sum\dfrac1{p_i-1}$。这玩意显然不超过 $1+\sum\dfrac1{p_i}$，而这个 $1$ exp 之后相当于乘个 $\mathrm e$，是常数可以忽略。而最劣情况下肯定是 $p_i$ 取了质数序列的一个前缀，我们如果找到这种情况下最大的质因子 $L$，那就是个质数倒数和 $\ln\ln L+\mathrm O(1)$，这样 $\sigma(m)=\mathrm O(m\exp\ln\ln L)=\mathrm O(m\log L)$。现在想知道 $L$ 是什么级别。 那 $L$ 显然不超过 $P(\left\lfloor\log_2 m\right\rfloor)$，其中 $P(n)$ 表示第 $n$ 个质数。而有结论 $P(n)=\mathrm O(n\log n)$，于是 $L=\mathrm O(\log m\log\log m)$，所以 $\sigma(m)=\mathrm O(m\log\log m+m\log\log\log m)=\mathrm O(m\log\log m)$。事实上 1e5 以内的因数和不超过 4e5，很符合预期。 ```cpp int qu, m; map<ti3, int> mp; void mian() { qu = read(), m = read(); REP(m0, 1, m) if(m % m0 == 0) { int fnm1 = 0, fn = 1 % m0, n = 1; do { int d0 = gcd(fnm1, m0), m00 = m0 / d0; ti3 t(d0, m00, (ll)fn * inv(fnm1 / d0, m00) % m00); if(mp.find(t) == mp.end()) mp[t] = n; swap(fnm1, fn), (fn += fnm1) %= m0, ++n; } while(fnm1 != 0 || fn != 1 % m0); } while(qu--) { int a = read(), b = read(); if(a == 0) { puts("0"); continue; } b = (m - b) % m; int d = gcd(gcd(a, b), m); int a0 = a / d, b0 = b / d, m0 = m / d; int d0 = gcd(b0, m0); int b00 = b0 / d0, m00 = m0 / d0; int ans = mp[mt(d0, m00, (ll)a0 * inv(b00, m00) % m00)]; prt(ans ? ans : -1), pc('\n'); } } ```