1、数论

2、组合计数

3、高斯消元

4、简单博弈论

1.1质数

质数的定义范围：大于1的正整数，如果只包含1和本身这两个约数，那么这个数就是质数，或者叫素数。

1.2质数的判定 – 试除法

bool check(int x) {
    if (x == 1) return 0;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) return 0;
    return 1;
}

复杂度O( $\sqrt{ n }$ )

1.3分解质因数 – 试除法

$n$ 最多只包含一个大于$\sqrt{n}$的质因子。

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

复杂度：O( $\sqrt{ n }$ )，最好复杂度是：O($\log{n}$)

1.4质数筛法

算法0 朴素筛法 $O(n\log(n))$

(1).做法:把2~(n-1)中的所有的数的倍数都标记上,最后没有被标记的数就是质数.
(2).原理:假定有一个数p未被2~(p-1)中的数标记过,那么说明,不存在2~(p-1)中的任何一个数的倍数是p,
也就是说p不是2~(p-1)中的任何数的倍数,也就是说2~(p-1)中不存在p的约数,因此,根据质数的定义可知，p是质数.

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

复杂度分析需要数学知识：（调和级数求极限）
$$ \lim_{n\to \infty } (1+\frac{1}{2} +\frac{1}{3} + … + \frac{1}{n}) = lne + C $$
其中$C$是欧拉常数，约等于$0.577$ 左右

算法1 埃氏筛法$O(nloglogn)$，由古希腊杰出的数学家发明
每次扫到一个还没有被标记的数，它就是质数，然后标记这个质数的所有倍数。

（原理是如果一个数是合数，那么它必然能被前面的某个质数所筛掉）

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

复杂度计算：

本来要筛n次，目前来说只需要筛 $\frac{n}{ln(n)}$

（原理是素数定理，在$1 \sim n$ 中有 $\frac{n}{ln(n)}$个质数。）

，估算起来大概是$O(n)$，但是实际上是$O(nloglogn)$

$1 \sim n$中，只计算质数项的话，”1/2+1/3+1/5+…+1/n”的大小约为 $\log(\log(n))$

算法2 线性筛法，又称为欧拉筛法$O(n)$
仍然是扫到一个未被标记的，它就是质数。
否则，这个算法的思路是：每个合数只被它最小的质因子筛掉。

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

2.约数

2.1试除法求一个正整数的所有约数：

vector<int> get_divisors(int x)
{
    vector<int> res ;
    for(int i=1; i<=n/i; i++){
        if(n % i == 0 ){
            res.push_back(i);
            if (i != n/i) res.push_back(n/i);
        }
    }
    sort(res.begin() , res.end() );
    return res;
}

复杂度是：$O(\sqrt{n})$

注意里面有个sort排序，所以有些同学认为是$nlog(n)$，其实是不对的，因为这里$1 \sim n $的个数中总的约数的个数，等于倍数的个数，所以$1$的倍数有个$n$个，$2$的倍数有$n/2$个,…,$n$的倍数有个$1$个，加起来$ n (1 + 1/2 + 1/3 + …)$，这个是所有的n个数的总的约数个数，平均来看，每个数的约数个数为$\log(n)$个，所以这里的排序复杂度为$ \log(n) * \log( \log(n) )$。

2.2约数个数：
$$ (\alpha_1 + 1 ) (\alpha_2 + 1 ) (\alpha_3 + 1 ) …(\alpha_n + 1 ) $$

基于算术基本定理，一个正整数$N$，一定能被分解为若干个质数相乘的形式。
$$ N = p_1^{\alpha_1} * p_2^{\alpha_2} * p_3^{\alpha_3} * …p_n^{\alpha_n} $$

2.3约数之和：
$$ (p_1^{0} + p_1^{1} + … + p_1^{\alpha_1} ) * (p_2^{0} + p_2^{1} + … + p_2^{\alpha_2}) * … * (p_n^{0} + p_n^{1} + … + p_n^{\alpha_n}) $$

unordered_map<int, int> primes;
while (n -- )
{
    int x;
    cin >> x;
    for (int i = 2; i <= x / i; i ++ )
        while (x % i == 0)
        {
            x /= i;
            primes[i] ++ ;
        }

    if (x > 1) primes[x] ++ ;
}

LL res = 1;
for (auto p : primes)
{
    LL a = p.first, b = p.second;
    LL t = 1;
    while (b -- ) t = (t * a + 1) % mod;
    res = res * t % mod;
}

cout << res << endl;

2.4欧几里得算法：

如果 d | a，d | b，则 d | (a * x + b * y)。

辗转相除法的核心：

(a , b) = (b , a mod b)

证明：

其中 a mod b 写成：
$$ a \bmod b = a - \left \lfloor \frac{a}{b} \right \rfloor * b $$
得到 a mod b = a - k * b

证明方法：

左边出发，任意的一个公约数d，d | a 且 d | b，则 d | a - k * b，任意的d也能整除右边

右边出发，任意的一个公约数d,d| b 且d | a - k * b，则d | a - k * b + k * b，任意的d也能整除左边。

左右两边的公约数的集合是相同的，推出最大公约数也相等。

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