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 ;
}