@(学习笔记)[扩展欧几里得]
本以为自己学过一次的知识不会那么容易忘记, 但事实证明, 两个星期后的我就已经不会做扩展欧几里得了...所以还是写一下学习笔记吧
问题概述
求解: $$ax + by = (a, b)$$
Hint: ((a, b))表示(gcd(a, b))
分析解决
根据欧几里得算法(辗转相除法), $$(a, b) = (b, a % b)$$
所以有$$ax + by = (a, b) = (b, a % b) = bx' + (a % b)y'$$
故我们递归计算$$bx' + (a % b)y' = (b, a % b)$$
又因为$$bx' + (a % b)y' = bx' + (a - blfloor frac{a}{b}
floor)y' = ay' + b(x' - lfloor frac{a}{b}
floor y)$$
所以我们得到(x = y', y = x' - lfloor frac{a}{b}
floor y).问题解决.
总结: 大致步骤如下:
- 辗转相除, 递归计算
- (x = y', y = x' - lfloor frac{a}{b} floor y')得到当前答案
应用
目前见到的还不是很多吧, 比如说这个中国剩余定理就需要用到exGCD了
题面:
http://192.168.102.138/JudgeOnline/problem.php?cid=1165&pid=5
题解:
http://www.cnblogs.com/ZeonfaiHo/p/6722168.html