[AcWing 877] 扩展欧几里得算法

复杂度 $ O(log(n)) $

总体复杂度 $ 10^{5} \times log( 2 \times 10^{9} ) \approx 4 \times 10 ^{6} $

#include

using namespace std;

int exgcd(int a, int b, int & x, int & y)
{
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    int n;
    scanf("%d", &n);
    while (n --) {
        int a, b;
        scanf("%d %d", &a, &b);
        int x, y;
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }
    return 0;
}

1. 裴蜀定理
   若 $ a, b $ 是整数，且 $ gcd(a, b) = d $ ，那么对于任意的整数 $ x, y $ ，$ a \cdot x + b \cdot y $ 都一定是 $ d $ 的倍数，特别地，一定存在整数 $ x, y $ ，使 $ a \cdot x + b \cdot y = d $ 成立
   推论：$ a, b $ 互质的充要条件是存在整数 $ x, y $ ，使 $ a \cdot x + b \cdot y = 1 $
2. 扩展欧几里得算法
   ① $ b = 0 $ 时，$ gcd(a, b) = a $ ，即要使 $ a \cdot x + b \cdot y = a $ ，可取 $ x = 1, \ y = 0 $
   ② $ b \neq 0 $ 时，由欧几里得算法，$ (a, \ b) = (b, \ a \bmod b) $ ，得到 $ b \cdot y + (a \bmod b) \cdot x = d $ ，而 $ a \bmod b = a - \left \lfloor \frac{a}{b} \right \rfloor \cdot b $ ，即 $ b \cdot y + (a - \left \lfloor \frac{a}{b} \right \rfloor \cdot b) \cdot x = d $ ，整理得到 $ a \cdot x + b \cdot (y - \left \lfloor \frac{a}{b} \right \rfloor \cdot x) = d $
3. 扩展欧几里得算法（更好的思考方式）