扩展欧几里得算法与线性同余方程 裴蜀定理： 扩展欧几里得算法： 线性同余方程：
对于任意的正整数a， b一定存在非零x，y使得：ax + by = gcd(a, b)(a和b的最大公约数）。
性质：ax + by 的最小值就是 gcd(a,b)
-
扩展欧几里得算法：
求出系数x，y
1 #include <iostream> 2 #include <algorithm> 3 4 using namespace std; 5 6 int exgcd(int a, int b, int &x, int &y) 7 { 8 if (!b) 9 { 10 x = 1, y = 0; 11 return a; 12 } 13 int d = exgcd(b, a % b, y, x); 14 y -= a / b * x; 15 return d; 16 } 17 18 int main() 19 { 20 int n; 21 scanf("%d", &n); 22 23 while (n -- ) 24 { 25 int a, b; 26 scanf("%d%d", &a, &b); 27 int x, y; 28 exgcd(a, b, x, y); 29 printf("%d %d ", x, y); 30 } 31 32 return 0; 33 }
-
线性同余方程：
求出x使其满足 a * x = b ( % m)
原式又等于：
a * x = b + m * y
a* x + m * (-y) = b, 故此时如果 b 是 gcd（a, m) 的倍数，则有解，否则无解
如果有解通过扩展欧几里得算法求出 x ，再 乘 b / gcd（a,m）倍
1 #include <iostream> 2 #include <algorithm> 3 4 using namespace std; 5 6 typedef long long LL; 7 8 9 int exgcd(int a, int b, int &x, int &y) 10 { 11 if (!b) 12 { 13 x = 1, y = 0; 14 return a; 15 } 16 int d = exgcd(b, a % b, y, x); 17 y -= a / b * x; 18 return d; 19 } 20 21 22 int main() 23 { 24 int n; 25 scanf("%d", &n); 26 while (n -- ) 27 { 28 int a, b, m; 29 scanf("%d%d%d", &a, &b, &m); 30 31 int x, y; 32 int d = exgcd(a, m, x, y); 33 if (b % d) puts("impossible"); 34 else printf("%d ", (LL)b / d * x % m); 35 } 36 37 return 0; 38 }