青岛网站推广怎么选,珠海网站建设防,网页分析,青海海东住房和城乡建设局网站线性同余方程问题
线程同余方程问题是指 a x ≡ b ( m o d m ) ax \equiv b~(mod~m) ax≡b (mod m)#xff0c;给定 a a a、 b b b和 m m m#xff0c;找到一个整数 x x x使得该方程成立#xff0c;即使得 a x m o d m b ax~mod~mb ax mod mb#xff0c;随便返回任何一个…线性同余方程问题
线程同余方程问题是指 a x ≡ b ( m o d m ) ax \equiv b~(mod~m) ax≡b (mod m)给定 a a a、 b b b和 m m m找到一个整数 x x x使得该方程成立即使得 a x m o d m b ax~mod~mb ax mod mb随便返回任何一个解都可以。
例如 4 x ≡ 3 ( m o d 5 ) 4x \equiv 3~(mod~5) 4x≡3 (mod 5)那么 x x x的一个可能的解可以是 2 2 2。
接下来用扩展欧几里得算法尝试构造这个解。从 a x ≡ b ( m o d m ) ax \equiv b~(mod~m) ax≡b (mod m)可知一定存在一个 y y y使得 a ⋅ x m ⋅ y b a \cdot x m \cdot y b a⋅xm⋅yb
也就是说因为 a x ax ax模 m m m的余数是 b b b所以 a x ax ax一定可以表示成 m m m的整数 y y y倍再加上一个 b b b。也就是 a x − m y b ax - my b ax−myb
令 y ′ y y y y′y那么就是 a x m y ′ b ax my b axmy′b
因此原线性同余方程问题求 x x x有解等价于这个方程求 x x x和 y ′ y y′有解。而根据扩展欧几里得算法里所讨论的 a a a是 g c d ( a , m ) gcd(a,~m) gcd(a, m)的倍数 m m m也是 g c d ( a , m ) gcd(a,~m) gcd(a, m)的倍数所以它们拼到一起也必须是 g c d ( a , m ) gcd(a,~m) gcd(a, m)的倍数。
因此这个方程有解的充要条件是 b b b必须是 g c d ( a , m ) gcd(a,~m) gcd(a, m)的倍数也即 g c d ( a , m ) ∣ b gcd(a,~m)~|~b gcd(a, m) ∣ b 。
例题AcWing 878. 线性同余方程
这题最终结果要限制在int范围内因为 m m m也是在int范围内的并且 a x m y b ⇔ a ( k m r ) m y b ⇔ a r m ( a k y ) b ax my b \\ \Leftrightarrow a(km r) my b \\ \Leftrightarrow ar m(ak y) b axmyb⇔a(kmr)myb⇔arm(aky)b 也就是说把系数 x x x变成 r x m o d m r x~mod~m rx mod m时另一个系数只要从 y y y变成 a k y aky aky就可以了其中 k ⌊ x m ⌋ k \lfloor \frac{x}{m} \rfloor k⌊mx⌋。
所以可以直接把结果 x x x模 m m m一定也是一个合法的解并且满足在int范围内的要求。
#include iostreamusing namespace std;typedef long long LL;int exgcd(int a, int b, int x, int y) {if (!b) {x 1, y 0;return a;}int d exgcd(b, a % b, y, x);// d b * y (a % b) * x b * y (a - a / b * b) * x// a * x b * (y - a / b * x)y - a / b * x;return d;
}int main() {int t; cin t;while (t -- ) {int a, b, m; cin a b m;// ax % m b, ax my b, iff gcd(a, m) d | bint x, y;int d exgcd(a, m, x, y);if (b % d) puts(impossible);else cout (LL)x * (b / d) % m endl;}return 0;
}
