题解：P10383 「HOI R1」杂分选约
Killer_joke
·
·
题解
给出一个不同于官方题解的还原模意义下的分数的方法。
参考 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 。
下面我们说明唯一性，首先 $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$ 矛盾了。
因此这样的对应是唯一的且可以用欧几里得过程自然的求出。
核心代码：
```cpp
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);
}
```