扩展欧几里得
作者:
nurupo
,
2022-04-18 16:24:31
,
所有人可见
,
阅读 140
->ax + by = gcd(a , b)
当b 等于 0 时
a * x + 0 * y = a
解得x = 1 , y = 0
当b不等于 0 时
这里的x y 是指的递归下层的x y 不是ax + by = gcd(a , b)的x和y
->bx+(a%b)y=gcd(b,a%b)
->bx+(a - floor(a / b) * b) y = gcd(b , a % b)
经过整理:
->ay + b(x - floor(a / b) * y) = gcd(b , a % b)
所以说
上层x = 下层y
上层y = 下层x - floor(a / b) * 下层y
采用递归的方法:先算出下层x和下层y,在算出上层x和上层y
求一般的ax + by = c
gcd(a,b)|c的时候x,y才有解
用欧几里得求出ax0 + by0 = gcd(a , b)
两边同时乘以c / d 得
a(x0 * c / d) + b(y0 *c / d) = c
求得同解x = x0 * c / d , y = y0 * c / d
注解:ax0 + by0 = gcd(a , b)
有不唯一得解:
a(x0 - b / d) + b(y0 + a / d) = gcd(a , b)就是一组解
x = x0 - b / d * k (k为整数)
y = y0 + a / d * k