前言
在关于数论的学习中,求解二元一次不定方程是很重要的,在学习求解二元一次不定方程之前,要先了解欧几里得算法和扩展欧几里得算法。
关于数论的学习
欧几里得算法
欧几里得算法就是辗转相除法,欧几里得算法中 ( x , y ) 的最大公约数与 ( y , xmod 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 和 yx = 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;}*/}}