AX+BY=C不定方程之解

引理一：辗转相除法 gcd(a,b)=gcd(b,a%b)

int gcd(int a,int b){
 if(b==)  return a;
 gcd(b,a%b);
}
           

引理二：裴蜀定理 ax+by=c 有解,当且仅当c|gcd(a,b)

扩展欧几里得定理：

首先对于ax+by=gcd(a,b),当b=0时，令x=1,y=0即可得到一组解

对于一般情况

ax1+by1=gcd(a,b)                                 (1)

             bx2+(a%b)y2=gcd(b,a%b)                           (2)  

       又    gcd(a,b)=gcd(b,a%b)                              （3）

           （1）-（3）得   

             ax1+by1=bx2+(a%b)y2                              (4)

         对于c语言中int型“/”符号有a%b=a-(a/b)*b                  (5)

           (4)(5) 整理得

          ax1+by1=ay2+b(x2-(a/b)y2) 

          即x1=y2,y1=x2-(a/b)y2

          这样的过程递归下去，最终a%b即下一次的b会等于0，此时符合特解
          ，再由特解递归上去，得到x1,y1.
           

代码如下图：

int exgcd(int a,int b,int &x,int &y){
if(b==){
    x=;
    y=;
    return a;
}
  int r=exgcd(b,a%b,x,y);
  int temp=x;       
  x=y;               
  y=temp-(a/b)*y;
  return r;         //r=gcd(a,b)
}
           

此时对于一般的ax+by=c，首先由裴蜀定理，c|gcd(a,b)时有解，那么

令c=gcd(a,b)*t

   ax+by=c → ax+by=gcd(a,b)*t →  a(x/t)+b(y/t)=gcd(a,b)

   也就是说 求出ax1+by1=gcd(a,b)之后 

   x=x1*t ,y=y1*t     →    x=x1*(c/gcd(a,b))  y=y1*(c/gcd(a,b))
           

完整代码如下：

#include <bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
if(b==){
    x=;
    y=;
    return a;
}
  int r=exgcd(b,a%b,x,y);
  int temp=x;       
  x=y;
  y=temp-(a/b)*y;
  return r;
}
int main(){
int a,b,c,x,y,gcd,t,
scanf("%d%d%d",&a,&b,&c);
gcd=exgcd(a,b,x,y);
t=c/gcd;
int x1=x*t,y1=y*t;
printf("%d %d\n",x1,y1);
return ;
}