（扩展）欧几里得算法模板

发表于 更新于 分类于
本文字数： 341 阅读时长 ≈ 1 分钟

欧几里得算法：$ O(log^n)$

1
2
3
4
//求两个整数的最大公约数：gcd(a, b) = gcd(b, a % b)
LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

扩展欧几里得算法：$ O(log^n)$

1
2
3
4
5
6
7
//求解二元一次方程：ax + by = gcd(a,b)
LL ext_gcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0LL) {x = 1LL; y = 0LL; return a;} //不妨假设 y=0，则x=1
    LL res = ext_gcd(b, a % b, x, y);
    LL tmp = x; x = y, y = tmp - a / b * y; //x'=y,y'=x-a/b*y
    return res; //返回上一个状态
}
0%