noip知识点总结之--欧几里得算法和扩展欧几里得算法
一、欧几里得算法
名字非常高大上的不一定难，比如欧几里得算法。。。其实就是求两个正整数a, b的最大公约数（即gcd），亦称辗转相除法
需要先知道一个定理：
gcd(a, b) = gcd(b, a mod b) (其中a mod b != 0) 或 b (其中a mod b == 0)
证明：
后半部分呢。。。是废话，于是只要证明前半部分即可。
不妨设g = gcd(a, b)，于是有 a = g * A, b = g * B 且 (A, B) = 1
故gcd(b, a mod b) = gcd(g * B, (g * A) mod (g * B)) = g * gcd(B, A mod B)
若gcd(B, A mod B) != 1，我们可以得到：
存在g‘ > 1，使g‘ | B且g‘ | A mod B，故g‘ | A， 与(A, B) = 1矛盾！
故gcd(B, A mod B) = 1，也即gcd(b, a mod b) = g * 1 = g = gcd(a, b)
证毕。。。（貌似搞烦了？）
于是就可以做了。。。时间复杂度是O(log(max(a, b)))
十分简单地code：（只有一行额。。。）
1 int gcd(int a, int b){ 2 return !b ? a : gcd(b, a % b); 3 }
应用的话。。。除了求gcd(a, b)以外。。。
貌似还可以求a，b的最小公倍数lcm(a, b) = a * b / gcd(a, b)（废话+1。。。）
但是许多地方都用得到gcd。。。还是挺重要的
二、扩展欧几里得算法
Now，我们已经会求了gcd(a, b)了。。。
而同时有一个叫裴蜀定理（搞得像吃的"焙薯"一样。。。饿了>.< 唔~）：
若gcd(a, b) = 1，则存在x, y，使a * x + b * y = 1（证略）
改一改就变成了：
对任意的a和b，存在x, y，使a * x + b * y = gcd(a, b)
而x, y的计算是可以在上面求解gcd(a, b)中一起完成的。。。推一下就出来了。。（有便加深记忆）
此处不再赘述，请直接参考code：
1 int extend_gcd(int a, int b, int &x, int & y){ 2 if (!b){ 3 x = 1, y = 0; 4 return a; 5 } 6 int res = extend_gcd(b, a % b, x, y), tmp = x; 7 x = y; 8 y = tmp - a / b * y; 9 return res; 10 }
而求出的(x, y)有可能会大（小）的非常离谱，于是就需要进行调整。。。
不定方程的通解形式大家都会吧。。。
扩展欧几里德算法的应用主要有以下三方面：
（1）求不定方程
（2）求模线性方程（线性同余方程）
（3）求模的逆元
作为noip的复习嘛。。。（1）就是本来的用处，（2）（3）应该不会考的说（奇怪的flag）
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
