1. 质数

试除法判断质数 O(根号n)

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;
}

试除法分解质因数 O(根号n)

void divide(int x)
{
    for(int i = 2; i <= x / i; i ++)
    {
        if(x % i == 0)
        {
            int s = 0;
            while(x % i == 0)
            {
                x /= i;
                s ++;
            }
            cout << i << ' ' << s << endl;
        }
    }    
    if(x > 1) cout << x << ' ' << 1 << endl;
    puts("");

}

朴素筛法求质数

预处理1 ~ n 时间复杂度O(nlogn),每一次查询的时间复杂度是O(1)

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

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

埃氏筛法求质数

预处理1 ~ n 时间复杂度O(nloglogn),近似O(n),每一次查询的时间复杂度是O(1)

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

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

线性筛法求质数

预处理1 ~ n 时间复杂度O(n),每一次查询的时间复杂度是O(1)
n只会被最小质因子筛掉

int primes[N], cnt;//primes存储已经发现的素数，处理到i时，把小于等于i的数都扔到数组里
bool st[N];

void get_primes(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;//加上会变成线性的神奇优化
        }
    }
}

亚线性筛法求质数 min25

时间复杂度<O(n)
CSND大佬讲的min25

2. 约数

3. 欧拉函数

4. 快速幂

每一次询问的时间复杂度`O(logn)

作用：以log的速度求出某个数的n次方

原理：2 ^ 18 -> 4 ^ 8 * 4 -> 16 ^ 4 * 4 -> 256 ^ 2 * 4

int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;//k % 2 == 0 等价于 k & 1
        k >>= 1;//k /= 2 等价于 k >>= 1
        a = (LL)a * a % p;
    }

    return res;
}

其他情况

当a和mod固定，b的范围不大(<le7),可以预处理a的所有次方，预处理的时间复杂度O(n),每一次询问O(1)

acwing 89 a^b

5. 拓展欧几里得算法

6. 中国剩余定理

7. 求组合数

8. 容斥原理

9. 博弈论

10. 简单的整除问题

acwing 4426 整除子串