C++ 二進制一次不定方程巧妙求解——運用擴充歐幾裡得算法

前言

在關于數論的學習中，求解二進制一次不定方程是很重要的，在學習求解二進制一次不定方程之前，要先了解歐幾裡得算法和擴充歐幾裡得算法。

關于數論的學習

歐幾裡得算法

歐幾裡得算法就是輾轉相除法，歐幾裡得算法中 ( x , y ) 的最大公約數與 ( y , x mod y ) 的最大公約數相同。

證明：設  y = k*x+b ，則 b = y % x 

           設 d 是 ( x ,y ) 的公約數

           則 d 能整除 x 和 y ,因為 b = y - k*x = a1*d - k*a2*d = d*( a1-k*a2 )

           是以 d 也能整除 b 

           是以 ( x , y ) 的最大公約數與 ( y , x%y ) 的最大公因數相同

擴充歐幾裡得算法

對于不完全為 0 的非負整數 a，b，gcd（a，b）表示 a，b 的最大公約數，必然

存在兩個整數 x，y ，使得 gcd（a，b）=a*x+b*y。

1. 當 b = 0時， x = 1 , y = 0

2.a>b>0時

證明：a*x+b*y = gcd( a，b)

有歐幾裡得算法可知

b*x1+( a % b )*y1 = gcd( b , a%b )

則a*x1+ b*y1= b*x2+ (a mod b)*y2;

是以a*x1+ b*y1= b*x2+ (a - [a / b] * b)*y2=a*y2+ b*x2- [a / b] * b*y2;

（a-[a/b]*b即為mod運算。[a/b]代表取小于等于a/b的最大整數）

也就是a*x1+ b*y1 == a*y2+ b*(x2- [a / b] *y2);

是以x1=y2

y1=x2- [a / b] *y2

關于求解 a*x+b*y=c的二進制一次不定式

根據上面的擴充歐幾裡得算法可知，若要讓 a*x+b*y=c成立，則 c 必須是 gcd( a , b ) 的倍數，否則會沒有整數解，那麼由于a*x1+b*y1=gcd( a , b )，是以 x 一定是 x1 的（c / gcd( a , b )）倍，y 一定是 y1 的（c / gcd( a , b )）倍。（剛讀可能很難了解，多讀幾遍就會明白）是以 x = x1*（c / gcd( a , b )）, y = y1*（c / gcd( a , b )）

這隻是一組特解，我們可以通過它，求出通解

而其他通解一定滿足

x0 = x + b / gcd( a , b ) * t

y0 = y - a  / gcd( a , b ) * t

其中 t 為任意數

代碼

結合代碼了解

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
 
int a , b , c , T ;
 
int ex( int a , int b , int &x , int &y )
{
    if(  b == 0 )
    {
        x = 1 ;
        y = 0 ;
        return a; 
    }
    else
    {
        int u = ex( b , a % b , y , x );
        y -= x *( a/b );
        return u ;
    }
}
 
int main()
{
    scanf("%d", &T );
    for(int h = 1 ; h <= T ; ++ h )
    {
        scanf("%d%d%d", &a , &b ,&c );
        int x = 0 ,y  = 0 ;
        int p = ex( a, b , x , y );//求最小公約數和滿足 a*x+b*y=gcd(a,b) 的 x 和 y
        x = x * ( c / p );
        y = y * ( c / p );
        cout<<x << " "<< y <<endl; //這裡隻輸出特解
        /*通解
            for(int i = -10000 ; i <= 100000 ; ++ i ) {
                y0 = y - a/p*i;
                x0 = x + b/p*i;
            }
        */
    }
}