关于noip 2012 day2 同余方程的问题这道题如果求得的结果是一个负数时需要利用 同余原理 x%b+b 将x转换为正的.求这个方法是怎么推出来的.

来源:学生作业帮助网 编辑:作业帮 时间:2024/11/06 07:14:56

关于noip 2012 day2 同余方程的问题这道题如果求得的结果是一个负数时需要利用 同余原理 x%b+b 将x转换为正的.求这个方法是怎么推出来的.
关于noip 2012 day2 同余方程的问题
这道题如果求得的结果是一个负数时需要利用 同余原理 x%b+b 将x转换为正的.求这个方法是怎么推出来的.

关于noip 2012 day2 同余方程的问题这道题如果求得的结果是一个负数时需要利用 同余原理 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 % b