之前简单的总结了下扩欧，这次来说说扩欧具体有哪些用法
总的来说扩展欧几里德算法的应用主要有以下两个方面：
（1）求解不定方程；
（2）求解模线性方程（线性同余方程）与逆元；

（1）求解不定方程
所谓不定方程就是形如：ax+by=c 我们通过扩欧可以知道若 c mod Gcd(a, b)=0,则该方程存在整数解，否则不存在整数解。
由上面的推导,我们知道,我们可以使用 ExGcd： ax + by = Gcd( a, b ) 求出一组解 ( x0 , y0 ) 使其满足 a * x0 + b * y0 = Gcd( a, b )，令d=Gcd(a,b)
令 A = a/d , B = b/d, C = c/d 带入原式得：Ax+By=C,又因为Gcd(A,B)=1,由扩欧得Ax+By=1,易得一组解x1,y1得Ax1+By1=1,两边同时乘以C得Ax1C+By1C=C,通过观察,我们可以知道二元组 ( x1C, y1C ) 是 Ax+By=C的一组解,使其满足 Ax + By = C,所以 ( x1C, y1C ) 是 ax + by = c 的一组解.但是满足方程的解无穷多个通解为：x+b/gcd(a,b)i y-a/gcd(a,b)i，i为整数。
所以 解不定方程代码为：
//不定方程
void linear_equation(int a, int b, int c, int &x, int &y)
{
int d = exgcd(a, b, x, y);
if (c%d)
return ;
int k = c/d;
x *= k; y *= k; // 一组解
return ;
}

（2）求解模线性方程（线性同余方程）与逆元：
同余方程 ax≡b (mod n)对于未知数 x 有解，当且仅当 gcd(a,n) | b。且方程有解时，方程有 gcd(a,n) 个解。
求解方程 ax≡b (mod n) 相当于求解方程 ax+ （-ny）= b, (x, y为整数)。
　　//ax = b (mod n) 即 (ax) mod n = b mod n
　算法导论上有两个定理：
　　定理一：设d = gcd(a, n), 假定对整数x', y', 有d = ax' + ny'， 如果d|b, 则方程ax = b(mod n)有一个解的值为x0, 满足：、
　　　　　　x0 = x'(b/d)(mod n）
　　定理二：假设方程ax = b(mod n)有解， x0是方程的任意一个解， 则方程对模n恰有d个不同的解， 分别为： xi = x0 + i * (n / d), 其中 i = 1,2,3......d - 1
　　有了这两个定理， 解方程就不难了。
代码如下：
bool modular_linear_equation(int a, int b, int n) {
int x, y, x0, i;
int d = exgcd(a, n, x, y);
if (b%d)
return false;
x0 = x(b/d)%n; //特解
for(i = 0; i < d; i++)
printf("%d\n", (x0 + i(n/d))%n);
return true;
}

同余方程ax≡b (mod n)，如果 gcd(a,n)== 1，则方程只有唯一解。
在这种情况下，如果 b== 1，同余方程就是 ax=1 (mod n ),gcd(a,n)= 1。
这时称求出的 x 为 a 的对模 n 乘法的逆元。
对于同余方程 ax= 1(mod n )， gcd(a,n)= 1 的求解就是求解方程
ax+ ny= 1，x, y 为整数。这个可用扩展欧几里德算法求出，原同余方程的唯一解就是用扩展欧几里德算法得出的 x 。
代码如下：
ll inv(ll a, ll n) {
ll d, x, y;
d = exgcd(a, n, x, y);
return (d == 1) ? (x%n + n)%n : -1;
}

提供一些题目：poj2115 poj2142 poj1061。hdu1576.hdu2115. ZOJ3609 ZOJ3593 HDU2669