前言

在关于数论的学习中，求解二元一次不定方程是很重要的，在学习求解二元一次不定方程之前，要先了解欧几里得算法和扩展欧几里得算法。

关于数论的学习

欧几里得算法

欧几里得算法就是辗转相除法，欧几里得算法中 ( 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;}*/}}