关于noip 2012 day2 同余方程的问题
发布网友
发布时间：1天前
共1个回答
热心网友
时间：21小时前
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 <= 0 ? x0 % b + b : x0 % b)。
至于为什么x0加上（或减去）的是b的某个倍数而不是另外某个比b小的数的倍数，是因为如果x0加上（或减去）某个比b小的数，就找不到能使等式成立的y了。
