算法学习（一）——欧几里德算法&扩展欧几里得算法

最大公约数/欧几里德算法（gcd）

欧几里德算法又称辗转相除法，是用于求最大公约数的方法，证明可以度娘。

个人简单脑补就是a和b两个数的模还是a和b的最大公约数

int类型

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

long long类型的

long long gcd(long long a, long long b) {return a%b==0 ? b : gcd(b, a%b);}

扩展欧几里得算法（exgcd）

概念：

对于不完全为0的非负整数a,b

必存在整数x,y，满足ax+by = gcd(a, b)

运用：

求解ax+by=c，用扩展欧几里得求得后*c/gcd(a,b)

求a*x≡1(mod p)

即求ax+py=1=gcd(a,b)/gcd(a,b)

也就是先求出ax+py=gcd(a,b)

然后x=x/gcd(a,b)即可

注意：x可能为负的，需要x=x+p

代码

typedef long long ll;

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

搬运自CSDN：https://blog.csdn.net/yueyue200830/article/details/85333585