问题引入

给出整数 a ， b ， n ，问方程 ax + by = n 什么时候有整数解？如何求出所有的整数解？

有解的充分必要条件是 gcd(a,b) 整除 n

简单解释一下，令 a = gcd(a,b) a’ ， b = gcd(a,b) b’ ,有 ax + by = gcd(a,b)(a’x+b’y) = n,如果 x ， y ，a’ , b’ 都是整数的话，那么 n 必须是 gcd(a,b) 的倍数才有解。

例如 4x+6y = 8、2x+3y = 4 有整数解，而 4x+6y = 7没有整数解。
如果确定有解，一种解题的方法是先找到一个解(x₀,y₀),那么通解就为：
x = x₀ + bt , y = y₀ – at (t 是任意整数)
利用拓展欧几里得算法便可以求出特解(x₀,y₀)

拓展欧几里得算法

当方程符合ax + by = gcd(a,b)时，可用拓展欧几里得算法求出(x₀,y₀),如下：

void gcdEx(int a,int b,int &x,int &y) { if(b == 0){         x=1;         y=0; return; } gcdEx(b,a%b,x,y); int tmp = x;     x = y;     y = tmp - (a/b)*y; } 

求任意方程 ax + by = n 的一个整数解

用拓展欧几里得算法得出方程 ax + by = gcd(a,b) 的一个特解后，利用它可以进一步得出任意方程 ax + by = n 的一个解，步骤如下：

1. 判断方程 ax + by = n 是否有整数解，有解的条件是 gcd(a,b) 可以整除 n
2. 用拓展欧几里得算法求 ax + by = gcd(a,b) 的一个解(x₀,y₀)
3. 在 ax₀ + by₀ = gcd(a,b) 两边同时乘以
   ${n above{0.5pt} gcd(a,b)}$

   gcd(a,b)n​ , 得：
   
   ${ax_0n above{0.5pt} gcd(a,b)}$

   gcd(a,b)ax0​n​ +
   ${by_0n above{0.5pt} gcd(a,b)}$

   gcd(a,b)by0​n​ = n

4. 对照 ax + by = n，得到它的一个解(x^’₀,y^’₀) 为：
   x^’₀ =
   ${x_0n above{0.5pt} gcd(a,b)}$

   gcd(a,b)x0​n​ ， y^’₀ =
   ${y_0n above{0.5pt} gcd(a,b)}$

   gcd(a,b)y0​n​

综上总的代码为:

//拓展欧几里得算法 void gcdEx(int a,int b,int &x,int &y);//参加上方 int main() { int a,b,n,x(0),y(0);     cin>>a>>b>>n; if(n%__gcd(a,b) == 0){ //第一步判断方程是否有整数解 gcdEx(a,b,x,y);//第二步求方程 ax+by=gcd(a,b) 的一个特解         x = x*n/__gcd(a,b); //第三步计算 ax+by=n 的解         y = y*n/__gcd(a,b);         cout<<x<<" "<<y<<endl; } return 0; } 

应用场合

1. 求解不定方程
2. 求解模的逆元
3. 求解同余方程