非常简易的还原分数方法

手机

英国房地产因利率上升陷入困境房价正以2011年来最快速度下跌

宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

非常简易的还原分数方法

2023-07-09 09:12:19 来源：博客园

(资料图)

感谢 @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 recover(LL x, LL p){    vector 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 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;}

关键词：