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:(只有一行额。。。)

 int gcd(int a, int b){
return !b ? a : gcd(b, a % b);
}

应用的话。。。除了求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:

 int extend_gcd(int a, int b, int &x, int & y){
if (!b){
x = , y = ;
return a;
}
int res = extend_gcd(b, a % b, x, y), tmp = x;
x = y;
y = tmp - a / b * y;
return res;
}

而求出的(x, y)有可能会大(小)的非常离谱,于是就需要进行调整。。。

不定方程的通解形式大家都会吧。。。

扩展欧几里德算法的应用主要有以下三方面:

(1)求不定方程

(2)求模线性方程(线性同余方程)

(3)求模的逆元

作为noip的复习嘛。。。(1)就是本来的用处,(2)(3)应该不会考的说(奇怪的flag)

上一篇:Django_调查问卷


下一篇:mysql下将分隔字符串转换为数组