最大公约数（Greatest Common Divisors）。

欧几里得算法

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

拓展欧几里得算法

int exgcd(int a, int b, int &x, int &y) {    if (!b) { x = 1; y = 0; return a; }    int result = exgcd(b, a % b, x, y);    int temp = x; x = y; y = temp - a / b * y;    return result;}

同余方程

应用拓展欧几里得算法。如洛谷P1082：

/* Luogu 1082 同余方程 * Au: GG * ax ≡ 1 (mod b) * ax + by = 1 */#include 
    
     using namespace std;int exgcd(int a, int b, int &x, int &y) {    if (!b) { x = 1; y = 0; return a; }    int result = exgcd(b, a % b, x, y);    int temp = x; x = y; y = temp - a / b * y;    return result;}int main() {    int a, b, x, y;    scanf("%d%d", &a, &b);    exgcd(a, b, x, y);    printf("%d\n", (x + b) % b);    return 0;}