exgcd 求出的 gcd

运行下面这段程序：

本节模型：exgcd(a, b, x, y) 返回 gcd，并通过引用参数带回 a·x + b·y = gcd 的一组 x、y；inv_ex(a, p) 用它求逆元。

#include <array>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

long long exgcd(long long a, long long b, long long& x, long long& y) {
    // 扩展欧几里得：返回 g = gcd(a, b)，并求出 a*x + b*y = g 的一组 x、y
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long inv_ex(long long a, long long p) {
    // 用 exgcd 求 a 关于 p 的逆元（要求 gcd(a, p) = 1）
    long long x, y;
    exgcd(a % p, p, x, y);
    return (x % p + p) % p;
}

int main() {
    long long x, y;
    cout << exgcd(30, 12, x, y) << endl;
}

（本题用 g++ -std=c++17 -O0 编译。）