p7325

chenxia25 · 2022-03-27 16:23:29 · 题解

首先通过分析 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}，则

以上用到了不等式 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，很符合预期。

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');
    }
}