浅谈欧几里得算法和扩欧

· · 个人记录

引入

给定两个整数a,b求gcd(a,b)别告诉我你不知道gcd

 

1.欧几里得算法求最大公约数

利用性质 \gcd(a,b)==\gcd(b,a\%b)

采用递归或非递归实现

递归版：

int gcd(int x, int y)
{
    if(!)
        return x;
    return gcd(y, x % y);
}

非递归版：

int x, y;
while(y)
{
    int r = x % y;
    x = y;
    y = r;
}//x即为gcd(x, y)

有了\gcd就可以求出\operatorname{lcm}别告诉我你不知道\operatorname{lcm}

利用性质：\gcd(x,y)=\dfrac{x \times y}{\operatorname{lcm}(x,y)}

证明：记\gcd(x,y)=d,则有x=d\times m,\; y=d \times n\;,故\;\operatorname{lcm}(x,y)=mn\;

\therefore xy=\gcd(x,y) \times \operatorname{lcm}(x,y)$ $\therefore\gcd(x,y)=\dfrac{x \times y}{\operatorname{lcm}(x,y)} 
int lcm(int x, int y)
{
    return x * y / gcd(x, y);
}

 

2.扩展欧几里得算法

前置芝士——\gcd小性质：

若a,b皆为非0的任意整数，则\gcd(a,b)为a,b的线性集合\{ax+by\mid x,y\in Z\}的最小正元素（证明太长懒得写）

1.扩欧就能解出满足下列条件的整系数x,y

\gcd(a,b)=ax+by

证明：

\because \gcd(a,b)=\gcd(b,a\%b) \therefore ax+by=bx_1+(a\%b)y_1 \therefore ax+by=bx_1+[a-(a/b)]y_1 \therefore ax+by=ay_1+b[x_1-(a/b)y_1] \therefore x=y_1,\;y=x_1-(a/b)y_1

所以就可以在求\gcd(a,b)的同时递归求解

int exgcd(int a, int b, int &x, int &y)
{
    if (!b) 
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;
    return d;
}

2.求解乘法逆元

乘法逆元，请在另一篇博客阅读

完结撒花！！！

求赞