参考：http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html
1 /* 2 gcd求最大公约数，两数相乘在除gcd可以求最小公倍数 3 */ 4 int gcd(int a, int b) 5 { 6 return b ? gcd(b, a % b) : a; 7 } 8 9 /* 10 exgcd 11 12 学习网址：http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html 13 14 扩展欧几里德算法的应用主要有以下三方面： 15 （1）求解不定方程； 找出一对整数(x, y), 使得 a*x + b*y = gcd(a, b). 16 （2）求解模线性方程（线性同余方程）； 17 （3）求解模的逆元； 18 19 结论1：若方程 ax + by = c 的一组整数解为（x0, y0）, 20 则它的任意整数解都可以写成(x0 + k * b', y0 + k * a'),其中 a' = a / gcd(a, b), b' = b / gcd(a, b), k 为任意整数. 21 22 结论2：设a, b, c为任意整数, g = gcd(a, b), 方程 a*x + b*y = g 的一组解是(x0, y0), 则当 c 是 g 的倍数时 23 a*x + b*y = c 的一组解是(x0*c/g, y0*c/g);当 c 不是 g 的倍数时无整数解. 24 */ 25 int exgcd(int a, int b, int &x, int &y) 26 { 27 if(b == 0) { 28 x = 1; 29 y = 0; 30 return a; 31 } 32 int r = exgcd(b, a % b, x, y); 33 int t = x; 34 x = y; 35 y = t - a / b * y; 36 return r; 37 } 38 39 /* 40 (1) : 解不定方程 a * x + b * y = c 41 */ 42 bool linear_equation(int a, int b, int c, int &x, int &y) 43 { 44 int d = exgcd(a, b, x, y); 45 if(c % d) { //没有整数解 46 return false; 47 } 48 int k = c / d; 49 x = x * k, y = y * k; //求得的是其中一组解 50 return true; 51 } 52 53 /* 54 (2) : 求解模线性方程的解集 : a * x ≡ b (mod n) 55 可以写成：a * x + n * y = b 56 */ 57 bool modular_linear_equation(int a,int b,int n) 58 { 59 int x, y, x0, div; 60 int d = exgcd(a, n, x, y); //解集共有d个数 61 if(b % d) { 62 return false; 63 } 64 x0 = x * (b / d) % n; //最小整数解 65 div = n / d; 66 if(div < 0) div = -div; 67 //每一个解的间隔是 n/d ,共有 d 个解 68 //如果有负数要变成正数 69 /* 70 求最小整数解: ans = x0 % div; 71 if(ans <= 0) ans += div; 72 73 就是: ans = (x0 % div + div) % div; 74 return ans; 75 */ 76 for(int i = 1; i <= d; i++) { 77 printf("%d ", (x0 + i * div) % n); 78 } 79 return true; 80 } 81 82 /* 83 (3) : 求解模的逆元：形如 a * x ≡ b (mod n) 的方程，如果gcd(a, n) == 1, 则方程只有唯一解 84 在这种情况下,如果b == 1,同余方程就是 a * x ≡ 1 (mod n), gcd(a, n) = 1 85 这时求出的 x 为 a 的对模 n 乘法的逆元 86 用拓展欧几里得可以求出 x 87 */