Math

判定质数

判定质数

假设 $d | n$ ，则有 $\frac{n}{d} | n$ ，不妨设 $d \lt \frac{n}{d}$，则 $d < \sqrt{n}$，

因此试除法判定质数的判断条件可以写为：

1
for(int i = 2; i <= n / i; ++ i)

质数筛

任意一个合数 $m$ 都可以写成 $m = p \times q$ ，其中 $p$ 为最小质因子，因此可以用线性筛。

1
2
3
4
5
6
7
8
9
10
11
12
bool st[N];	//用以记录哪些数被筛除
int primes[N], cnt;
void ger_primes() {
    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;
        }
    }
}
// 外层循环保证遍历，每一个 q ，内层循环保证用最小质因子 p 筛掉合数， 并且当  i % primes[j] == 0 时，break， 因为此后就不是用最小质因子筛选

约数

任意一个数都有 $m = p_1^{x_1} \times p_2^{x_2} \times … \times p_n^{x_n}$，其中 $P_i \in 质数$，根据组合原理，则数 $m$ 的 约数个数 为 $(x_1 + 1) \times (x_2 + 1) \times … \times (x_n + 1)$。

约数之和 就是上述每一种取值求和，意即：$\sum{d} = \sum{x_1=0}^{a_1}\sum{a2=0}^{x_2}…\sum{a_n=0}^{x_n}(p_1^{a_1} \times p_2^{a_2} \times … \times p_n^{a_n})$

整理得：$\sum{d}=\prod{i=0}^{n}(\sum{a_i=0}^{x_i}p_i^{a_i})$

最大公约数: 

1
2
3
int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a；
}

假设 $d | a, d | b, a \% b = a - kb$，则有 $d | a - kb$，因此 $d$ 也是 $(b, a \% b)$ 的约数；反之，假设 $d | b, d | a\%b$，意即 $d | b, d | a - kb$，则 $d | a - kb + kb$，即 $d$ 也是 $(a,b)$ 的约数。

欧拉函数

$1 \sim N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\phi(N)$ ，在算数基本定理中有 $\phi(N)=N\prod_{i=1}^{n}(1 - \frac{1}{p_i})$ 。

快速幂

本质上是二分快速求幂。

1
2
3
4
5
6
7
8
9
10
typedef long long LL;
int qmi(int a, int b. imt p) {
    LL res = 1 % p;
    while(b) {
        if(b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1; 
    }
    return res;
}

逆元

若整数 $b,m$ 互质，并且对于任意的整数 $a$，如果满足 $b | a$ ，则存在一个整数 $x$，使得 $\frac{a}{b} \equiv a \times x \pmod m$，则称 $x$ 为 $b$ 的模 $m$ 乘法逆元，记为 $b^{-1} \pmod m$。

$b$ 存在乘法逆元的充要条件是 $b$ 与 模数 $m$ 互质，当 $m$ 为质数时，$b^{m-2}$ 即为 $b$ 的乘法逆元。

扩展欧几里德算法

对于数 $a,b$，求出一组数 $x,y$，满足 $a \times x + b \times y = gcd(a,b)$。

当 $b=0$ 时，显然有 $gcd(a,b) = a, x = 1, y = 0$;

当 $b \neq 0$ 时，$a \times x + b \times y = gcd(a,b)=gcd(b, a \% b)$;

进一步，$b \times x’ + (a - \left\lfloor a/b \right\rfloor* b) \times y’ = gcd(a, a \% b)$;

整理可得：$x = y’, y = x’ - \left\lfloor a/b \right\rfloor* y’$

1
2
3
4
5
6
7
8
9
10
int exgcd(int a, int b, int &x, int &y){
    if(!b) {
        x = 1, y = 0;
        return a;
    }
    int x1, y1;
    int d = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;
    retu
}

线性同余方程

$a \times x \equiv b \pmod m$ 意即 $a \times x - b$ 一定是 $m$ 的倍数，因此线性同余方程等价为 $a \times x + m \times y = b$；

根据贝祖定理，上述等式有解的充要条件是 $gcd(a, m) | b$；

因此通过扩展欧几里德算法求出特解 $x_0$ 后，$x = x_0 \times \frac{b}{gcd(a,m)} \% m$