GabWiki | GabWiki

数学

向上取整

$⌈ \frac{a}{b} ⌉ = ⌊ \frac{a + b - 1}{b} ⌋$ 。

C++

int ceil = (a + b - 1) / b

int ceil = (a + b - 1) / b

加法原理

完成一个工程可以有 $n$ 类办法， $a_{i} (1 \leq i \leq n)$ 代表第 $i$ 类方法的数目。那么完成这件事共有 $S = a_{1} + a_{2} + \dots + a_{n}$ 种不同的方法。

乘法原理

完成一个工程需要分 $n$ 个步骤， $a_{i} (1 \leq i \leq n)$ 代表第 $i$ 个步骤的不同方法数目。那么完成这件事共有 $S = a_{1} \times a_{2} \times \dots \times a_{n}$ 种不同的方法。

算术基本定理

任何一个大于 $1$ 的正整数都能分解为有限个质数的幂的乘积：

n = p_{1}^{α_{1}} \times p_{2}^{α_{2}} \times \dots \times p_{k}^{α_{k}}, p_{1} < p_{2} < \dots < p_{k}

其中 $α_{i} \in Z$ ， $p_{i}$ 都是质数，且 $p_{1} < p_{2} < \dots p_{k}$ ；在不计次序的意义下，该表示唯一。

裴蜀定理

裴蜀定理，又称贝祖定理（Bézout's lemma）。是一个关于最大公约数的定理。

其内容是：

设 $a, b$ 是不全为零的整数，则存在整数 $x, y$ ，使得 $a x + b y = gcd (a, b)$ 。

平方和公式

\sum_{i = 1}^{n} i^{2} = 1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6}

质数

试除法判质数

模板代码：

JavaC++

Java

boolean isPrime(int n) {
    if (n < 2) return false;
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) return false;
    }
    return true;
}

boolean isPrime(int n) {
    if (n < 2) return false;
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) return false;
    }
    return true;
}

C++

bool is_prime(int n) {
    if (n < 2) return false;
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) return false;
    }
    return true;
}

bool is_prime(int n) {
    if (n < 2) return false;
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) return false;
    }
    return true;
}

时间复杂度： $O (\sqrt{n})$ 。

试除法分解质因数

分解质因数（Prime Factorization）：根据算术基本定理，每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。

模板题：【数学】分解质因数。

原理：试除法，枚举 $2 \dots n$ 中的所有质数，如果 $i$ 是 $n$ 的质因子，就把 $n$ 中的 $i$ 除干净。

模板代码：

JavaC++

Java

void pf(int n) {
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) {
            int s = 0;
            while (n % x == 0) {
                n /= x;
                ++s;
            }
            System.out.println(x + " " + s);
        }
    }
    if (n > 1) System.out.println(n + " 1");
}

void pf(int n) {
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) {
            int s = 0;
            while (n % x == 0) {
                n /= x;
                ++s;
            }
            System.out.println(x + " " + s);
        }
    }
    if (n > 1) System.out.println(n + " 1");
}

C++

void pf(int n) {
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) {
            int s = 0;
            while (n % x == 0) {
                n /= x;
                ++s;
            }
            printf("%d %d\n", x, s);
        }
    }
    if (n > 1) printf("%d 1\n", n);
}

void pf(int n) {
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) {
            int s = 0;
            while (n % x == 0) {
                n /= x;
                ++s;
            }
            printf("%d %d\n", x, s);
        }
    }
    if (n > 1) printf("%d 1\n", n);
}

时间复杂度：

最差： $O (\sqrt{n})$ ；
最好： $O (\log N)$ 。

其中枚举的 $i$ 一定是质数，因为：当枚举到 $i$ 的时候，已经把 $[2, i - 1]$ 中的质因子都除掉了，当 if (n % i == 0) 成立的时候， $n$ 中已经没有任何在 $[2, i - 1]$ 范围内的质因子，又因为 $n$ 是 $i$ 的倍数，所以 $i$ 也没有任何在 $[2, i - 1]$ 范围内的因子，所以此时 $i$ 一定是质数。

筛质数

模板题：【数学】筛质数。

朴素筛

原理：

枚举 $x \in [2, n]$ ， $x$ 的倍数一定是合数，所以可以在枚举到 $x$ 的时候筛掉所有 小于等于 $n$ 的 $x$ 的倍数 。
而在枚举到 $p \in [2, n]$ 的时候，如果 $p$ 还没有被筛掉，说明 $p$ 不是 $x \in [2, p - 1]$ 中任意一个数的倍数，所以 $p$ 一定是质数。

模板代码：

Java

int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int x = 2; x <= n; ++x) {
        if (!isNotPrime[x]) primes[cnt++] = x;
        for (int k = 2; k * x <= n; ++k) isNotPrime[k * x] = true;
    }
    return cnt;
}

int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int x = 2; x <= n; ++x) {
        if (!isNotPrime[x]) primes[cnt++] = x;
        for (int k = 2; k * x <= n; ++k) isNotPrime[k * x] = true;
    }
    return cnt;
}

时间复杂度： $O (N \log N)$ 。

埃氏筛

原理：要得到自然数 $n$ 以内的全部质数，把不大于 $\sqrt{n}$ 的所有质数的倍数筛除，剩下的就都是质数。

证明：根据算术基本定理：每一个大于 $1$ 的正整数都能分解成有限个质数的幂的乘积，且由于是从小到大枚举，在枚举到某个合数之前，一定先会枚举到它的质因数，也就是说所有的合数都会被它的质因数筛掉。

模板代码：

Java

int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int x = 2; x <= n; ++x) {
        if (!isNotPrime[x]) {
            primes[cnt++] = x;
            for (int k = 2; k * x <= n; ++k) isNotPrime[k * x] = true;
        }
    }
    return cnt;
}

int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int x = 2; x <= n; ++x) {
        if (!isNotPrime[x]) {
            primes[cnt++] = x;
            for (int k = 2; k * x <= n; ++k) isNotPrime[k * x] = true;
        }
    }
    return cnt;
}

时间复杂度： $O (N \log \log N)$ 。

线性筛（欧拉筛）

原理：线性筛保证了每个合数都只被其最小质因子筛掉。

模板代码：

JavaC++

Java

int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int x = 2; x <= n; ++x) {
        if (!isNotPrime[i]) primes[cnt++] = x;
        for (int i = 0; primes[i] <= n / x; ++i) {
            isNotPrime[primes[i] * x] = true;
            if (x % primes[i] == 0) break;
        }
    }
    return cnt;
}

int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int x = 2; x <= n; ++x) {
        if (!isNotPrime[i]) primes[cnt++] = x;
        for (int i = 0; primes[i] <= n / x; ++i) {
            isNotPrime[primes[i] * x] = true;
            if (x % primes[i] == 0) break;
        }
    }
    return cnt;
}

C++

int cnt, primes[N];
bool np[N];

int sieve(int n) {
    for (int x = 2; x <= n; ++x) {
        if (!np[x]) primes[cnt++] = x;
        for (int i = 0; primes[i] <= n / x; ++i) {
            np[primes[i] * x] = true;
            if (x % primes[i] == 0) break;
        }
    }
    return cnt;
}

int cnt, primes[N];
bool np[N];

int sieve(int n) {
    for (int x = 2; x <= n; ++x) {
        if (!np[x]) primes[cnt++] = x;
        for (int i = 0; primes[i] <= n / x; ++i) {
            np[primes[i] * x] = true;
            if (x % primes[i] == 0) break;
        }
    }
    return cnt;
}

时间复杂度： $O (N)$ 。

线性筛是如何保证每个合数只会被其最小质因子筛掉的？

当 x % primes[i] == 0 时，说明此时遍历到的 $p_{i}$ 不是 $x$ 的质因子，那么 ** $p_{i}$ 一定小于 $x$ 的最小质因子 **，所以 $p_{i} \cdot x$ 的最小质因子就是 $p_{i}$ ；
当 x % primes[i] != 0 时，说明 $x$ 的最小质因子是此时的 $p_{i}$ ，因此 $p_{i} \cdot x$ 的最小质因子依旧应该是 $p_{i}$ ，但如果继续枚举的话，我们就把 $p_{i + 1} \cdot x$ 这个数筛掉了，虽然这个数也是合数，但是筛掉它的时候并不是用它的最小质因数筛掉的 ，而是利用 $p_{i + 1}$ 和 $x$ 把它删掉的，而这个数的最小质因数其实是 $p_{i}$ ，如果不在这里退出循环的话，就会发现有些数是被重复筛了的。

勒让德定理

在正数 $n!$ 的质因数分解中，质数 $p$ 的指数记作 $ν_{p} (n!)$ ，则：

ν_{p} (n!) = \sum_{i = 1}^{⌊ \log_{p} n ⌋} ⌊ \frac{n}{p^{k}} ⌋

模板代码：

C++

int count(int n, int p) {
    int res = 0;
    while (n) res += n /= p;
    return res;
}

int count(int n, int p) {
    int res = 0;
    while (n) res += n /= p;
    return res;
}

约数

试除法求所有约数

模板代码：

C++

set<int> get_divisors(int n) {
    set<int> divisors;
    for (int i = 1; i <= n / i; ++i) {
        if (n % i == 0) {
            divisors.insert(i);
            divisors.insert(n / i);
        }
    }
    return divisors;
}

set<int> get_divisors(int n) {
    set<int> divisors;
    for (int i = 1; i <= n / i; ++i) {
        if (n % i == 0) {
            divisors.insert(i);
            divisors.insert(n / i);
        }
    }
    return divisors;
}

时间复杂度： $O (\sqrt{n})$ 。

int 范围内，约数最多的数其约数有 $1536$ 个。

约数个数

求约数个数

模板题：【数学】约数个数。

原理：

根据算术基本定理把 $n$ 质因数分解为： $n = p_{1}^{α_{1}} \times p_{2}^{α_{2}} \times \dots \times p_{k}^{α_{k}}$ ；
那么 $n$ 的约数个数为： $f (n) = \prod_{i = 1}^{k} (α_{i} + 1) = (α_{1} + 1) (α_{2} + 1) \dots (α_{k} + 1)$ 。

证明：

显然， $p_{1}^{α_{1}}$ 的约数为 $p_{1}^{0}, p_{1}^{1}, \dots, p_{1}^{k}$ ，同理： $p_{i}^{α_{i}}$ 的约数为 $p_{i}^{0}, p_{i}^{1}, \dots, p_{i}^{i}$ ；
实际上 $n$ 的约数是在 $p_{1}^{α_{1}}, p_{2}^{α_{2}}, \dots p_{k}^{α_{k}}$ 每个数的约数中分别挑一个相乘得来的，那么 $n$ 的每个约数就都可以被分解为 $d = p_{1}^{β_{1}} \times p_{2}^{β_{2}} \times \dots \times p_{k}^{β_{k}}$ （其中 $0 \leq β_{i} \leq α_{i}$ ）；
又根据算术基本定理：每一个数的质因数分解是唯一的，那么 $β_{i}$ 的所有组合就对应了 $n$ 的所有约数；
而每个 $β_{i}$ 都有 $0 \dots α_{i}$ 共 $α_{i} + 1$ 种选择，所以 $d$ 共有 $\prod_{i = 1}^{k} (α_{i} + 1)$ 个组合，那么 $n$ 也就有这么多个约数。

模板代码：

C++

// 求一个数的约数个数
int count_divisors(int n) {
    int cnt = 1;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                ++s;
            }
           	cnt *= s + 1;
        }
    }
    if (n > 1) cnt *= 2;
    return cnt;
}

// 求一个数的约数个数
int count_divisors(int n) {
    int cnt = 1;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                ++s;
            }
           	cnt *= s + 1;
        }
    }
    if (n > 1) cnt *= 2;
    return cnt;
}

时间复杂度：

最差： $O (\sqrt{n})$ ；
最好： $O (\log N)$ 。

一些与约数个数相关的性质

$1 \sim N$ 中所有数的约数个数之和总和约为 $N \log N$ 个；
$[0, 2 \times 10^{9}]$ 范围内的约数个数最多的数的约数约有 1600 个。

约数之和

模板题：【数学】约数之和。

原理：

根据算术基本定理把 $n$ 质因数分解为： $n = p_{1}^{α_{1}} \times p_{2}^{α_{2}} \times \dots \times p_{k}^{α_{k}}$ ；
那么 $n$ 的约数之和为：
$\begin{aligned} σ (n) & = \prod_{i = 1}^{k} (\sum_{j = 0}^{α_{k}} p_{i}^{j}) \\ = (p_{1}^{0} + p_{1}^{1} + p_{1}^{2} + \dots + p_{1}^{α_{1}}) (p_{2}^{0} + p_{2}^{1} + p_{2}^{2} + \dots + p_{2}^{α_{2}}) \dots (p_{k}^{0} + p_{k}^{1} + p_{k}^{2} + \dots + p_{k}^{α_{k}}) \end{aligned}$

证明：

显然， $p_{1}^{α_{1}}$ 的约数为 $p_{1}^{0}, p_{1}^{1}, \dots, p_{1}^{k}$ ，同理： $p_{i}^{α_{i}}$ 的约数为 $p_{i}^{0}, p_{i}^{1}, \dots, p_{i}^{i}$ ；
实际上 $n$ 的约数是在 $p_{1}^{α_{1}}, p_{2}^{α_{2}}, \dots p_{k}^{α_{k}}$ 每个数的约数中分别挑一个相乘得来的；
可知共有 $(α_{1} + 1) (α_{2} + 1) \dots (α_{k} + 1)$ 种挑法，即约数个数。
由乘法原理可知它们的和为：
$\begin{aligned} σ (n) & = \prod_{i = 1}^{k} (\sum_{j = 0}^{α_{k}} p_{i}^{j}) \\ = (p_{1}^{0} + p_{1}^{1} + p_{1}^{2} + \dots + p_{1}^{α_{1}}) (p_{2}^{0} + p_{2}^{1} + p_{2}^{2} + \dots + p_{2}^{α_{2}}) \dots (p_{k}^{0} + p_{k}^{1} + p_{k}^{2} + \dots + p_{k}^{α_{k}}) \end{aligned}$

模板代码：

C++

// 求一个数的约数之和
int sum_divisors(int n) {
    int sum = 1;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
			int tmp = 1;
            while (n % i == 0) {
                n /= i;
                tmp = i * tmp + 1;
            }
            sum *= tmp;
        }
    }
    if (n > 1) sum *= n + 1;
    return sum;
}

// 求一个数的约数之和
int sum_divisors(int n) {
    int sum = 1;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
			int tmp = 1;
            while (n % i == 0) {
                n /= i;
                tmp = i * tmp + 1;
            }
            sum *= tmp;
        }
    }
    if (n > 1) sum *= n + 1;
    return sum;
}

最大公约数

原理：辗转相除法（欧几里得算法）： $gcd (a, b) = gcd (b, a mod b)$ 。

证明：

已知 $a mod b = a - ⌊ \frac{a}{b} ⌋ \cdot b$ ，设 $c = ⌊ \frac{a}{b} ⌋$ ，则现在要证明 $gcd (a, b) = gcd (b, a - c \cdot b)$ ；
对于 $gcd (a, b)$ ，设 $d ∣ a, d ∣ b$ ：
- 则显然有 $d ∣ a x + b y, x, y \in Z$ ，当 $x = 1, y = c$ 时， $d ∣ a - c \cdot b$ ；
- $d ∣ b, d ∣ a - c \cdot b$ 同时成立，则有 $gcd (a, b) \subseteq gcd (b, a - c \cdot b)$ 。
对于 $gcd (b, a - c \cdot b)$ ，设 $d ∣ b, d ∣ a - c \cdot b$ ：
- 则显然有 $d ∣ a - c \cdot b + c \cdot b \Rightarrow d ∣ a$ ；
- $d ∣ a, d ∣ b$ 同时成立，则有 $gcd (b, a - c \cdot b) \subseteq gcd (a, b)$ 。
$gcd (a, b) = gcd (b, a - c \cdot b)$ 得证，同时 $gcd (a, b) = gcd (b, a mod b)$ 也成立。

模板代码：（递归实现）

Java / C++

C++

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

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

欧拉函数

公式求欧拉函数

详细介绍及原理：欧拉函数 - OI Wiki。

若在算术基本定理中： $n = p_{1}^{α_{1}} \times p_{2}^{α_{2}} \times \dots \times p_{k}^{α_{k}}$ 。

那么 $n$ 的欧拉函数： $ϕ (n) = n \times \prod_{i = 1}^{k} (1 - \frac{1}{p_{i}}) = n \times \frac{p_{1} - 1}{p_{1}} \times \frac{p_{2} - 1}{p_{2}} \times \dots \times \frac{p_{k} - 1}{p_{k}}$ 。

模板代码：

C++

typedef long long LL;

// 求一个数的欧拉函数
LL phi(int n) {
    LL res = n;
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) {
            while (n % x == 0) n /= x;
            res = res * (x - 1) / x;
        }
    }
    if (n > 1) res = res * (n - 1) / n;
    return res;
}

typedef long long LL;

// 求一个数的欧拉函数
LL phi(int n) {
    LL res = n;
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) {
            while (n % x == 0) n /= x;
            res = res * (x - 1) / x;
        }
    }
    if (n > 1) res = res * (n - 1) / n;
    return res;
}

时间复杂度： $O (\sqrt{N})$ 。

筛法求欧拉函数之和

求 $1 \sim n$ 中每个数的欧拉函数之和：

Java

long sumEulers(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1], phi = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!isNotPrime[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; ++j) {
            isNotPrime[primes[j] * i] = true;
            if (i % primes[j] == 0) {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    long res = 0L;
    for (int i = 1; i <= n; ++i) res += phi[i];
    return res;
}

long sumEulers(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1], phi = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!isNotPrime[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; ++j) {
            isNotPrime[primes[j] * i] = true;
            if (i % primes[j] == 0) {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    long res = 0L;
    for (int i = 1; i <= n; ++i) res += phi[i];
    return res;
}

时间复杂度： $O (N)$ 。

快速幂

详细介绍及原理：快速幂 - OI Wiki。

模板代码：

JavaC++

Java

long kasumi(long base, long exp, long mod) {
    long res = 1L;
    while (exp != 0) {
        if ((exp & 1) != 0) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

long kasumi(long base, long exp, long mod) {
    long res = 1L;
    while (exp != 0) {
        if ((exp & 1) != 0) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

C++

typedef long long LL;

LL kasumi(LL base, LL exp, LL mod) {
    LL res = 1LL;
    while (exp) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

typedef long long LL;

LL kasumi(LL base, LL exp, LL mod) {
    LL res = 1LL;
    while (exp) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

慢速乘

防止乘数及模数很大但还在 long long 范围内时直接做乘爆 long long 的问题。

JavaC++

Java

long slowMul(long a, long b, long m) {
    long c = 0L;
    while (b > 0) {
        if ((b & 1) != 0) c = (c + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return c;
}

long slowMul(long a, long b, long m) {
    long c = 0L;
    while (b > 0) {
        if ((b & 1) != 0) c = (c + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return c;
}

C++

typedef long long LL;

LL slow_mul(LL a, LL b, LL m) {
    LL c = 0LL;
    while (b) {
        if (b & 1) c = (c + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return c;
}

typedef long long LL;

LL slow_mul(LL a, LL b, LL m) {
    LL c = 0LL;
    while (b) {
        if (b & 1) c = (c + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return c;
}

扩展欧几里得算法

扩展欧几里得算法（Extended Euclidean algorithm, EXGCD），常用于求 $a x + b y = gcd (a, b)$ （裴蜀定理）的一组可行解。

过程

设：

$a x_{1} + b y_{1} = gcd (a, b)$

$b x_{2} + (a mod b) y_{2} = gcd (b, a mod b)$

由欧几里得算法可知： $gcd (a, b) = gcd (b, a mod b)$

所以：

\begin{aligned} a x_{1} + b y_{1} & = b x_{2} + (a mod b) y_{2} \\ a x_{1} + b y_{1} & = b x_{2} + (a - ⌊ \frac{a}{b} ⌋ \cdot b) y_{2} \\ a x_{1} + b y_{1} & = b x_{2} + a y_{2} - b ⌊ \frac{a}{b} ⌋ y_{2} \\ a x_{1} + b y_{1} & = a y_{2} + b (x_{2} - ⌊ \frac{a}{b} ⌋ y_{2}) \end{aligned}

因为 $a = a, b = b$ ，所以： ${\begin{cases} x_{1} = y_{2} \\ y_{1} = x_{2} - ⌊ \frac{a}{b} ⌋ y_{2} \end{cases}$ 。

将 $x_{2}, y_{2}$ 不断代入递归求解，直至 $b = 0$ 时： $a x + 0 y = a$ ，显然 ${\begin{cases} x = 1 \\ y = 0 \end{cases}$ 是一组解，此时退出递归。

模板代码

Java

int x, y;
    
int exgcd(int a, int b) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b);
    int t = x;
    x = y;
    y = t - a / b * y;
    return d;
}

int x, y;
    
int exgcd(int a, int b) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b);
    int t = x;
    x = y;
    y = t - a / b * y;
    return d;
}

线性同余方程

定义

形如：

a x \equiv b (\mod n)

的方程称为 线性同余方程（Congruence Equation）。其中，

数学 ​

向上取整 ​

加法原理 ​

乘法原理 ​

算术基本定理 ​

裴蜀定理 ​

平方和公式 ​

质数 ​

试除法判质数 ​

试除法分解质因数 ​

筛质数 ​

朴素筛 ​

埃氏筛 ​

线性筛（欧拉筛） ​

勒让德定理 ​

约数 ​

试除法求所有约数 ​

约数个数 ​

求约数个数 ​

一些与约数个数相关的性质 ​

约数之和 ​

最大公约数 ​

欧拉函数 ​

公式求欧拉函数 ​

筛法求欧拉函数之和 ​

快速幂 ​

慢速乘 ​

扩展欧几里得算法 ​

过程 ​

模板代码 ​

线性同余方程 ​

定义 ​

数学

向上取整

加法原理

乘法原理

算术基本定理

裴蜀定理

平方和公式

质数

试除法判质数

试除法分解质因数

筛质数

朴素筛

埃氏筛

线性筛（欧拉筛）

勒让德定理

约数

试除法求所有约数

约数个数

求约数个数

一些与约数个数相关的性质

约数之和

最大公约数

欧拉函数

公式求欧拉函数

筛法求欧拉函数之和

快速幂

慢速乘

扩展欧几里得算法

过程

模板代码

线性同余方程

定义