扩展欧几里德求解ax + by = c 的 最小正整数解 （ x, y）

欧几里德求解ax + by = c 的 最小正整数解 （ x, y）"/>

扩展欧几里德求解ax + by = c 的 最小正整数解 （ x, y）

大概思路 ：
第一步 ： 给出方程 ax + by = c 。
第二步 ： 算出 辗转相除法 gcd(a, b) 。
第三步 ： 运用 扩展欧几里德 ex_gcd（a, b）-》 ax + by = gcd(a,b) 的 一组解（x, y） 。
第三步： 根据 c % gcd(a, b) 判断是否 ax + by = c 有解 。
第四步 ： 根据 ax + by = c 的通解公式 x1 = (x + k * ( b / gcd(a, b) )) * (c / gcd(a, b) 令 b1 = b / gcd(a, b) , 所以 x1 的 最小正整数解 为 ： x1 = (x1 % b1 + b1) % b1, 对应的 y1 = （c - a*x1） / b.

代码如下 ：

/**function : work out ax + by = c  ->(x, y) and request that x is least positive integer.date : 2017.11.5author : LSCcode : c++
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
long long int x, y, d;// (x, y) ax+by = Gcd(a, b)的其中的一个解，d 是（a, b）最大公约数LL Gcd(LL a, LL b)// 欧几里德算法（辗转相除法）求解最大公约数
{return (b == 0)? a : Gcd(b, a%b);
}void ex_gcd(LL a, LL b)// 扩展欧几里德 算法
{if(b == 0){x = 1;y = 0;d = a;}else{ex_gcd(b, a%b);LL temp = x;x = y;y = temp - a/b*y;}
}int main()
{LL a, b, c, gcd;scanf("%lld%lld%lld", &a, &b, &c);gcd = Gcd(a, b);if(c % gcd != 0)// 判断是否有解printf("Impossible\n");else{ex_gcd(a, b);LL x1, y1, b1;b1 = b/gcd;x1 = (x + b1) * (c/gcd);x1 = (x1 % b1 + b1) % b1;// 求解出 x 的 最小正整数解y1 = (c - a*x1) / b;printf("x = %lld , y = %lld\n", x1, y1);}return 0;
}

下面再来一个压缩版本的比较短，但和上面计算出的结果都是一样的，我测试过了几组数据了！！！！

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;void extend_gcd(LL a, LL b, LL& d, LL& x, LL& y)
{if(!b){ d = a; x = 1; y = 0; }else { extend_gcd(b, a%b,d, y, x); y -= x*(a/b);}
}int main()
{LL a, b, c, d;LL x, y, x1, y1;cin >> a >> b >> c;extend_gcd(a, b, d, x, y);if(c % d != 0)printf("Impossible\n");else{LL b1 = b / d;x1 = (x + b1) * (c / d);x1 = (x1 % b1 + b1) % b1;y1 = (c - a*x1) / b;printf("x = %lld, y = %lld\n", x1, y1);}return 0;
}