自动搬运

查看原文

来自洛谷，原作者为

	Killer_joke 现实里的麻烦总是免费包邮的。

搬运于2025-08-24 22:57:26，当前版本为作者最后更新于2024-04-30 18:06:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给出一个不同于官方题解的还原模意义下的分数的方法。

参考 https://blog.csdn.net/EI_Captain/article/details/117172239 。

假设我们求得了 $\dfrac{a}{b} = q\mod M$ 而且我们知道 $a,b \leq A$ 。

那么我们有 $a=Mt+qb$ 其中 $|t| \leq A$。

我们考虑利用欧几里得过程还原这个东西。

考虑对 $M,q$ 求解 exgcd 的过程，我们实际上约减的每一步都给出一个 $a'=Mt'+qb'$ 的构造。

其中 $a'$ 逐渐减小到 $1$ ，所以我们一定可以找到一组 $a',b'$ 满足 $a'\leq A, |b'|\leq A$ 。

$b'$ 的值域就是 exgcd 值域上的最小性。

下面我们说明唯一性，首先 $a',b'$ 一定互质，假若不互质说明 $t',b'$ 也不互质，与 exgcd 能求出最大公约数矛盾。

那么假设存在一组 $c,d$ 满足 $\dfrac{c}{d}=\dfrac{a'}{b'}=q\mod M$。

作差可得 $b'c-a'd=kM$ 只要模数满足 $2A^2<M$, 这便与 $a',|b'|,c,|d'| \leq A$ 矛盾了。

因此这样的对应是唯一的且可以用欧几里得过程自然的求出。

核心代码：

auto approx(i128 p,i128 q,i128 A){
    i128 x=q,y=p,a=1,b=0;
    while(x>A){
        std::swap(x,y); 
        std::swap(a,b);
        a-=x/y*b,x%=y;
    }
    return std::make_pair(x,a);
}