「补档计划」欧几里得与扩展欧几里得算法

#include <bits/stdc++.h>

inline int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}

int main() {
    std::cout << std::__gcd(3, 9) << std::endl;
    std::cout << gcd(3, 9) << std::endl;
}

inline void exgcd(long a, long b, long &g, long &x, long &y) {
    !b ? (x = 1, y = 0, g = a) : (exgcd(b, a % b, g, y, x), y -= (a / b) * x);
}

inline bool linearEquation(long a, long b, long c, long &x, long &y) {
    register long g;
    exgcd(a, b, g, x, y);
    if (c % g) return false;
    register int k = c / g;
    x *= k, y *= k;
    return true;
}

inline bool modularLinearEquation(long a, long b, long c, long &ans) {
    register long x, y, g;
    exgcd(a, c, g, x, y);
    if (b % g) return false;
    ans = (x * (b / g) % (c / g) + (c / g)) % (c / g);
    return true;
}

inline long inv(const long num) {
    register long g, x, y;
    exgcd(num, MOD, g, x, y);
    return (x % MOD + MOD) % MOD;
}