对于
a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)
这样的方程，可以用扩展欧几里得算法exgcd求出一组通解。
根据欧几里得求gcd：
g c d ( a , b ) = g c d ( b , a % b ) gcd(a,b)=gcd(b,a\%b) gcd(a,b)=gcd(b,a%b)
可得
b x + ( a % b ) y = g c d ( b , a % b ) bx+(a\%b)y=gcd(b,a\%b) bx+(a%b)y=gcd(b,a%b)
根据
a % b = a ? ( a / b ) ? b a\%b=a-(a/b)*b a%b=a?(a/b)?b
可得
b x + a y ? ( a / b ) b ? y = g c d ( b , a % b ) bx+ay-(a/b)b*y=gcd(b,a\%b) bx+ay?(a/b)b?y=gcd(b,a%b)
化简得
a y + b ( x ? ( a / b ) y ) = g c d ( b , a % b ) ay+b(x-(a/b)y)=gcd(b,a\%b) ay+b(x?(a/b)y)=gcd(b,a%b)
令
x ′ = y , y ′ = ( x ? ( a / b ) y ) x'
= y , y'
= (x-(a/b)y) x′=y,y′=(x?(a/b)y)
可得
a x ′ + b y ′ = g c d ( b , a % b ) <
= >
a x + b y = g c d ( a , b ) ax'
+by'
=gcd(b,a\%b) <
=>
ax+by=gcd(a,b) ax′+by′=gcd(b,a%b)<=>ax+by=gcd(a,b)
根据
g c d ( a , 0 ) = a gcd(a,0)=a gcd(a,0)=a a x + b y = a ax+by=a ax+by=a
可以得出一组平凡解
x = 1 , y = 0 x=1,y = 0 x=1,y=0
【扩展欧几里得|扩展欧几里得算法求解不定方程||中国剩余定理】所以一直递归下去可以得出一组平凡解，然后再往回带得出 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)的一组解。
泛化来看不定方程
a x + b y = c ax+by=c ax+by=c
只有满足 c % g c d ( a , b ) = = 0 c\%gcd(a,b) == 0 c%gcd(a,b)==0才有解。
求解同余方程
a x ≡ bm o dn ax \equiv b\ mod\ n ax≡b mod n
a x = b + n y ax = b+ny ax=b+ny
令 y = -y
a x + n y = b ax+ny = b ax+ny=b
就转变成了上述形式
中国剩余定理
https://blog.csdn.net/niiick/article/details/80229217
https://www.cnblogs.com/freinds/p/6388992.html
推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- HDU 5528 Count a × b
- 线性同余方程组
- 数论|AtCoder Beginner Contest 156 C.Rally