质数

定义：在大于1的整数中，如果只包含1和其本身这两个约数，则称这个数为质数或者素数

（1）质数的判定--试除法

时间复杂度：O(sqrt(n))

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

（2）质因子判定--试除法

n中最多只包含一个大于sqrt(n)的质因子
时间复杂度：最好情况下：O(logn),最坏情况下：O(sqrt(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;
    cout << endl;
}

（3）筛质数法

遍历过程中将每个数所有的倍数删掉，剩下的就是质因子

朴素筛法

int primes[N], cnt;     // primes[]存储所有质数
bool st[N];         // st[x]存储x是否被筛掉

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

线性筛法

int primes[N], cnt;     // primes[]存储所有质数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    int cnt = 0
    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;//primes[j]一定是i的最小质因子 ，保证每个数是被其最小的质因子筛除的
        }
    }
}

约数

（1）试除法求n所有约数

时间复杂度：O(sqrt(n))

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

（2）约数个数和约数之和

//这两个公式非常重要，一定要记牢
如果 N = p1^c1 * p2^c2 * ... *pk^ck //N分解约数因子后
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

约数个数:

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main()
{
    int n;
    cin >> 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) res = res * (p.second + 1) % mod;

    cout << res << endl;

    return 0;
}

约数之和：

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main()
{
    int n;
    cin >> 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;

    return 0;
}

（3）欧几里得算法-求最大公约数

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;//b如果不是0，返回前者，否则返回后者
}

欧拉函数

表示1~n中与n互质的数的个数。（两个正整数只有公约数1时，此时两个正整数互质）

int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0) //说明i是x的质因子
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

线性筛法求欧拉函数--求1~N中每个数的欧拉函数

int primes[N], cnt;     // primes[]存储所有质数（素数）
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


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

欧拉定理：

费马定理：

快速幂--划重点！！！

解决问题：快速求出 a^k mod p 的结果，在O（logk）的时间范围内求出

求 m^k mod p，时间复杂度 O(logk)。

int qmi(int m, int k, int p)
{
    int res = 1, t = m;
    while (k) 
    {
        if (k&1) res = res * t % p;
        t = t * t % p;//t是记录拆分出来的值，例如上面的4^2^0 mod 10 的值
        k >>= 1;//k=k>>1
    }
    return res;
}

int qmi(int m, int k, int p)
{
    int res = 1;
    while (k) 
    {
        if (k&1) res = res * m % p;
        m = m * m % p;//m是记录拆分出来的值，例如上面的4^2^0 mod 10 的值
        k >>= 1;//k=k>>1
    }
    return res;
}

qmi(b,m-2,m)

扩展欧几里得算法

裴蜀定理：
对于任意正整数a,b，一定存在非零整数x,y使得 ax + by =（a,b）--a和b的最大公约数

a和b的最大公约数是a和b能凑出的最小整数

扩展欧几里得算法是对于任意的正整数a,b，都能求出非零整数x,y

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}

应用：求解线性同余方程

前提是b一定要是gcd(a,m)的倍数

中国剩余定理

高斯消元求解线性方程组，在n^3内求解出方程组的解

解有三种情况：
1.无解
2.无穷多组解
3.唯一解

用到了线性代数中的初等行列变换，转化成最简阶梯型矩阵（上三角矩阵）

• 把某一行乘一个非零的数
• 交换某两行
• 把某行的若干倍加到令一行

其中完美阶梯形矩阵指的是第一行有n个未知数，第二行有n-1个...，第n行有1个未知数

每次迭代结束都会固定一行，下一次迭代的第一步就不再考虑已经固定的行

const int N = 110
const double eps = 1e-6
// a[N][N]是增广矩阵
// 高斯消元之后，a[i][n]就是每个未知数的解
int gauss()
{
    int c, r;//行和列
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )   // 找到绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c])) //fabs是返回浮点数
                t = i;

        if (fabs(a[t][c]) < eps) continue;

        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);      // 将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];      // 将当前上的首位变成1
        for (int i = r + 1; i < n; i ++ ) {      // 用当前行将下面所有行的第c列消成0
            if (fabs(a[i][c]) > eps) {//当系数不是零的时候进行消零操作
                for (int j = n; j >= c; j -- ){
                    a[i][j] -= a[r][j] * a[i][c];
                }
            }
        }
        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps) //出现了0 = 非零的情况则无解
                return 2; // 无解
        return 1; // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];//a[j][n]就是xj的值

    return 0; // 有唯一解
}

求组合数

递推公式法求组合数 --O(N^2)

1<=b<=a<=2000

int N = 2010
int mod = 1e9 + 7
// c[a][b] 表示从a个苹果中选b个苹果的方案数
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

通过预处理逆元的方式求组合数 --O(NlogN)

1<=b<=a<=10^5

首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
如果取模的数是质数，可以用费马小定理求逆元
int qmi(int a, int k, int p)    // 快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 预处理阶乘的余数和阶乘逆元的余数 
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}

Lucas定理求组合数 -O(plogNlogp)

1<=b<=a<=10^18,1<=p<=10^5

若p是质数，则对于任意整数 1 <= m <= n，有：
    C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)

int qmi(int a, int k)       // 快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}


int C(int a, int b)     // 通过定理求组合数C(a, b)
{
    int res = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- )
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2) % p;
    }
    return res;
}


int lucas(LL a, LL b)
{
    if (a < p && b < p) return C(a, b);
    return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

分解质因数法求组合数

当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
    1. 筛法求出范围内的所有质数
    2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...
    3. 用高精度乘法将所有质因子相乘

int primes[N], cnt;     // 存储所有质数
int sum[N];     // 存储每个质数的次数
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;
        }
    }
}


int get(int n, int p)       // 求n！中p的次数
{
    int res = 0;
    while (n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}


vector<int> mul(vector<int> a, int b)       // 高精度乘低精度模板
{
    vector<int> c;
    int t = 0;//表示进位
    for (int i = 0; i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);//把个位取出来
        t /= 10;
    }

    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }

    return c;
}

get_primes(a);  // 预处理范围内的所有质数

for (int i = 0; i < cnt; i ++ )     // 求每个质因数的次数
{
    int p = primes[i];//当前的质数
    sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}

vector<int> res;
res.push_back(1);

for (int i = 0; i < cnt; i ++ )     // 用高精度乘法将所有质因子相乘
    for (int j = 0; j < sum[i]; j ++ )
        res = mul(res, primes[i]);

卡特兰数

给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为： 
Cat(n) = C(2n, n) / (n + 1)

容斥原理

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL

const int N = 20

int n,m
in p[N]
int main(){
    cin >> n >> m;
    for(int i=0 ; i < m ; i++ ) {
        cin >> p[i];
    }
    int res = 0; //用来存储答案
    for(int i=1 ; i < 1 << m ; i++){
        int t=1,cnt=0;//t用来存储质数的乘积，cnt表示当前的选择方案中包含几个1
        for(int j=0;j<m;j++){//从0开始枚举m位
                if(i>>j &1){
                    cnt++;
                    if((LL)t * p[j] > n){
                        t=-1;
                        break;
                    }
                    t *= p[j]
                }
         }
        if(t!=-1){
            if(cnt%2) res += n/t
            else res-= n/t
        }
    }

}

简单博弈论

NIM游戏

如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0

3^4 = 7

SG函数

有向图游戏的和：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 110, M = 10010;//N每堆石子个数，M石子堆数

int n, m;
int s[N], f[M];//s表示石子个数，f表示SG的值

int sg(int x)
{
    if (f[x] != -1) return f[x];

    unordered_set<int> S;//用来存储其可以到达的所有局面
    for (int i = 0; i < m; i ++ )
    {
        int sum = s[i];//当前石子的个数
        if (x >= sum) S.insert(sg(x - sum));
    }

    for (int i = 0; ; i ++ )//判断当前集合中不存在的最小自然数是多少
        if (!S.count(i))
            return f[x] = i;
}

int main()
{
    cin >> m;
    for (int i = 0; i < m; i ++ ) cin >> s[i];
    cin >> n;

    memset(f, -1, sizeof f);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }

    if (res) puts("Yes");
    else puts("No");

    return 0;
}