本文记录一些数论知识以及算法模板,涉及质数、约数、欧拉函数、(扩展)欧几里得、同余、乘法逆元、组合数。

一些数学符号说明

  1. $(x,y)$ 表示:$x,y$ 的最大公约数;$[x,y]$ 表示:$x,y$ 的最小公倍数。
  2. $a \equiv b(mod \ c)$ 表示:$a,b$ 模 $c$ 同余。(好吧这个同余于是恒等于伪装的)
  3. $a \mid b$ 表示:$a$ 整除 $b$。(如 $2$ 整除 $4$)
  4. $\lfloor \frac{a}{b} \rfloor,\ \lceil \frac{a}{b} \rceil$ 分别表示下取整、上取整。

质数

  1. 定义:大于 $1$ 的自然数,除了 $1$ 和自身,无法被其他任何自然数整除,称为质数也称素数。

  2. 素数定理:$1$~$N$ 中质数的数量大约为 $\frac{N}{lnN}$ 个。

  3. 算数基本定理:任何一个大于 $1$ 的正整数都能唯一分解为有限个质数的乘积,如下: $$ N = p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k} $$

  4. $N!$ 中质因子 $p$ 的个数为:

    $$ \lfloor \frac{N}{p} \rfloor + \lfloor \frac{N}{p^2} \rfloor + \lfloor \frac{N}{p^3} \rfloor + … + \lfloor \frac{N}{\lfloor p^{log_pN} \rfloor} \rfloor = \sum_{p^k \le N} \lfloor \frac{N}{p_k} \rfloor $$

模板跳转试除法判定质数埃氏筛法线性筛法分解质因数阶乘质因子个数

未完待续~

约数

欧拉函数

扩展欧几里得

同余

乘法逆元

组合数

矩乘




算法模板

试除法判定质数

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

埃氏筛法

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

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            for (int j = i + i; j <= n; j += i) st[j] = true;
        }
    }
}

线性筛法

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

void euler(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j ++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break; 
        }
    }
}

分解质因数

void divide(int x) { // 对x分解质因数
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) { 
            int s = 0;
            while (x % i == 0) x /= i, s++;
            printf("%d %d\n", i, s);
        }
    }
    if (n > 1) printf("%d %d\n", n, 1);
}

阶乘质因子个数

int s = 0; // n!中质因子p的个数
for (int k = n; k; k /= p) s += k / p;