非常简易的还原分数方法

感谢 @unputdownable

问题简述

给定素数 \(p\)，正整数 \(x\) 满足 \(1 \le x < p\)，则存在 \(\dfrac{a}{b} \equiv x \pmod p\)，即 \(a \equiv bx \pmod p\)。求一组 \(a, b\) 使得 \(\max\{|a|, ||b\}\) 尽可能小。

做法

考虑 \(a = bx + kp\)，则可以转写成 \(a = k(p \bmod x) \pmod x\)，即 \(\dfrac{a}{k} \equiv (p \bmod x)\)。这是一个子问题，转化形式类似欧几里得算法。顶多迭代 \(\log \min\{a, b\}\) 轮以后 \(x\) 就会变成 \(1\)，这时候停止。在每一层我们都能得到一个朴素解 \(\dfrac{x}{1} \equiv x \pmod p\)，即 \(a = x, b = 1\)；同时从下一层的某个解 \(k\) 还能还原出 唯一对应的 某个当前层的解 \(b = \dfrac{a - kp}{x}\)。这样从下往上不断还原，在最顶层（即原问题）我们可以得到 \(\log\min\{a, b\}\) 个不同的解。注意到实际上并不需要一步一步还原，因为 \(b \equiv x^{-1} \cdot a \pmod p\)，而 \(a\) 的数值是不会在传递中改变的，所以在每一层记录朴素解中 \(a\) 的数值（即当前的 \(x\)），在顶层求一次 \(x^{-1}\bmod p\)，就能 \(\Theta(\log \min\{a, b\}\)) 地得到这些所有解。求出最小解不需要约分。

接下来证明这样就得到了所有正整数解（负数解一定对应某个正数解，不需要求）。考虑任何一组解，把它带入 \(a = bx + kp\)，求出 \(k\)，不断传递到下一层。\(a\) 在这个过程中始终不变，而在解变得没有意义（\(k = 0\)）之前，\(b\) 一定会变成 \(1\)，这个时候就中止。那么从这一层开始向上传递求出的解就是这组解。所以所有解都可以被用这样的方式求出。

代码

LL kpow(LL x, LL k, LL p)
{
    LL r = 1;
    while (k)
    {
        if (k & 1) r = (__int128)r * x % p;
        x = (__int128)x * x % p;
        k >>= 1;
    }
    return r;
}

pair<LL, LL> recover(LL x, LL p)
{
    vector<LL> a;
    LL invx = kpow(x, p - 2, p), pp = p;
    while (x)
    {
        a.push_back(x);
        LL t = x;
        x = p % x;
        p = t;
    }
    pair<LL, LL> res{pp, pp};
    for (auto ca : a)
    {
        LL cb = (__int128)ca * invx % pp;
        ca = min(ca, pp - ca);
        cb = min(cb, pp - cb);
        if (max(res.first, res.second) > max(ca, cb))
            res = {ca, cb};
    }
    return res;
}