作业帮关于noip 2012 day2 同余方程的问题
来源：学生作业帮 编辑：拍题作业网作业帮 分类：数学作业 时间：2024/04/29 22:30:43
关于noip 2012 day2 同余方程的问题
这道题如果求得的结果是一个负数时需要利用 同余原理 x%b+b 将x转换为正的.求这个方法是怎么推出来的.
这道题如果求得的结果是一个负数时需要利用 同余原理 x%b+b 将x转换为正的.求这个方法是怎么推出来的.
a * x = 1 (mod b)等价于a * x + b * y = 1.
假设(x0, y0)是它的某一组解（可以用扩展欧几里得算法求出）,即a * x0 + b * y0 = 1,
那么有a * (x0 + k * b) + b * (y0 - k * a) = 1,其中k可以为负数、0、或正数.
所有等于x0 + k * b的数都可以是方程的解,其中最小的正整数就是(x0 %
假设(x0, y0)是它的某一组解（可以用扩展欧几里得算法求出）,即a * x0 + b * y0 = 1,
那么有a * (x0 + k * b) + b * (y0 - k * a) = 1,其中k可以为负数、0、或正数.
所有等于x0 + k * b的数都可以是方程的解,其中最小的正整数就是(x0 %