数论

质数

质数判定方法：试除法

分解质因数：试除法

试除法本来需要将i从2循环到x，但由于大于sqrt(x)的x的质因子最多只有一个，因此只需要将i从2循环到x/i即可。同时，若x在经过除法后仍然大于2，说明其本身就是一个质因子。这样可以由原来的$O(n)$复杂度降为$O(\sqrt n)$。

注意：优化后算法的最佳时间复杂度为$O(\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
int main() {
    
    int n;
    scanf("%d", &n);
    while(n--) {
        int x;
        scanf("%d", &x);
        for(int i = 2; i <= x / i; ++i) {
            int s = 0;
            while(x % i == 0) {
                s++;
                x /= i;
            }
            if(s > 0)
                printf("%d %d\n", i, s);
        }
        if(x > 1) printf("%d 1\n", x);
        printf("\n");
    }

    return 0;
}

筛质数

时间复杂度计算基础：

$$
1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}=\ln n+c
$$

埃式筛法

思想重要

对每个数进行标记，如果该数是质数，那么标记他整数倍除它本身之外的数为和数。时间复杂度为$O(n\log \log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;
bool st[N];
int main() {
    int n;
    scanf("%d", &n);
    int res = 0;
    for(int i = 2; i <= n; ++i) {
        if(!st[i]) {
            res++;
            for(int j = i << 1; j <= n; j += i) {
                st[j] = true;
            }
        }
    }
    printf("%d", res);
    return 0;
}

线性筛法

模板

$n$只会被最小的质因子筛掉…

比如说3是质数，就应该排除掉6，9，12，15，18…

知道了5是质数，应该排除掉10，15，20，25，30…

  1. 若$i\ %\ \text{primes[j]}==0$，primes[j]一定是primes[j]*i的最小质因子
  2. 若!=0，primes[j]一定小于i的所有质因子，primes[j]$\cdot$i也一定是priems[j]$\cdot$i的最小质因子

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;
bool st[N];
int prime[N], cnt;
void get_primes(int n) {
    for(int i = 2; i <= n; ++i) {
        // 如果前面没有判断出它是合数，说明它肯定是个素数
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0; prime[j] <= n / i; ++j) {
            st[prime[j] * i] = true; // 使用最小质因子prime[j]去筛除更大的数
            // 一个合数只需要使用其最小质因子去筛除就可以了
            if(i % prime[j] == 0) break; // primes[j]是i的最小质因子
        }
    }
}
int main() {
    int n;
    scanf("%d", &n);
    get_primes(n);
    printf("%d", cnt);
    return 0;
}

每一个合数会被筛出，由于是用最小质因子筛出的，因此只会被筛一次，因此时间复杂度为$O(n)$。

约数

所有约数

可以使用试除法求出一个数的所有约数，时间复杂度为$O(n)$。实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

void _find(int x) {
    stack<int> s;
    for(int i = 1; i <= sqrt(x); ++i) {
        if(x % i == 0) {
            printf("%d ", i);
            s.push(x / i);
        }
    }
    while(!s.empty()) {
        if(s.top() != sqrt(x)) printf("%d ", s.top());
        s.pop();
    }
    printf("\n");
}

int main() {
    int n;
    scanf("%d", &n);
    while(n--) {
        int x;
        scanf("%d", &x);
        _find(x);
    }
    return 0;
}

约数个数

问：给定$n$个正整数$a_i$，求出这些数的乘积的约数个数。

设$a_i$可以表示为$p_1^{\beta_{11}}p_2^{\beta_{12}}p_3^{\beta_{13}}…p_n^{\beta_{1n}}$

那么$n$个正整数的积可以表示为$p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}…p_n^{\alpha_n}$，其中$\alpha_i$为任意非负整数，因此约数个数可以表示为
$$
(\alpha_1+1)(\alpha_2+1)(\alpha_3+1)\cdot …\cdot(\alpha_n+1)
$$
怎么像在做数学分析题一样…这样就可以求出来了…
参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1e9+7;
int main() {
    int n;
    scanf("%d", &n);
    long long int res = 1;
    unordered_map<int,int> primes;
    while(n--) {
        int x;
        scanf("%d", &x);
        for(int i = 2; i <= x / i; ++i) {
            while(x % i == 0) {
                x /= i;
                primes[i]++;
            }
        }
        if(x > 1) primes[x]++;
    }
    for(auto p : primes) {
        res = res * ((long long int)p.second+1) % mod;
    }
    printf("%lld", res);
    return 0;
}

具体实现时又是老三样问题了，primes怎么想到哈希的；大数乘法一定要用long long int；for语句执行到sqrt(x)就可以结了。
`

约数之和

问：给定$n$个正整数$a_i$，求出这些数的乘积的约数之和。

乘积结果表示同上，每个约数就是从每个$p_k$中挑选$[0,\alpha_k]$次方的数。这样结果就为：
$$
(1+p_1+p_1^2+…+p_1^{\alpha_n})\cdot(1+p_2+…)\cdot…
$$
参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1e9+7;
int main() {
    long long int res = 1;
    int n;
    scanf("%d", &n);
    unordered_map<int,int> hash;
    while(n--) {
        int x;
        scanf("%d", &x);
        for(int i = 2; i <= x / i; ++i) {
            while(x % i == 0) {
                x /= i;
                hash[i]++;
            }
        }
        if(x > 1) hash[x]++;
    }
    long long int tmp;
    long long int temp = 1;
    for(auto h : hash) {
        tmp = 0;
        temp = 1;
        for(int i = 0; i <= h.second; ++i) {
            tmp = (tmp + temp) % mod;
            temp = (temp * h.first) % mod;
        }
        res = (res * tmp) % mod;
    }
    printf("%lld", res);
    return 0;
}

最大公约数

欧几里得法

Steps:大数放a中，小数放b中；
求a/b的余数；
若temp=0则b为最大公约数；
如果temp!=0则把b的值给a,temp的值给a；
返回第二步。

证明：
设$a%b = a - kb$ 其中$k = a/b$(向下取整)
若d是(a,b)的公约数 则知 $d|a$ 且 $d|b$ 则易知 $d|a-kb$ 故$d$也是$(b,a%b)$ 的公约数
若d是$(b,a%b)$的公约数 则知 $d|b$ 且 $d|a-kb$ 则 $d|a-kb+k*b = d|a$ 故而$d|b$ 故而 $d$也是(a,b)的公约数
因此$(a,b)$的公约数集合和$(b,a%b)$的公约数集合相同 所以他们的最大公约数也相同 证毕
实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
void gcd(int a, int b) {
    if(a < b) swap(a, b);
    while(a % b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    printf("%d\n", b);
}
int main() {
    int n;
    scanf("%d", &n);
    while(n--) {
        int a, b;
        scanf("%d%d", &a, &b);
        gcd(a, b);
    }
    return 0;
}

时间复杂度是$O(n)$。

欧拉定理

欧拉函数：
$1$到$N$中与$N$互质的个数被称为欧拉函数，即为$\phi(N)$。
若$N=p_1^{a_1}p_2^{a_2}p_3^{a_3}…$，则：
$$
\phi(N)=N\cdot\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}\frac{p_3-1}{p_3}\cdot …
$$
那么这个公式是如何得出的呢？
首先，对于$N$个数，需要去除$p_i$的倍数，因此当前个数为：
$$
N-N/p_1-N/p_2-N/p_3-…-N/p_k
$$
由于对于$p_ip_j$来说减去了两次，因此还需要加上：
$$
N/(p_1p_2)+N/(p_1p_3)+…
$$
对于$p_ip_jp_k$来说，在单位减去了3次，在两个数组合也减去了三次，因此还要在后面加上一次才行…
如此循环下去，知道所有乘积的组合都被考虑进去即可，该式最终可以化成上面的表达式。（也是容斥原理的基本思路）
该算法的时间复杂度为$O(\sqrt n)$，瓶颈在求所有的质因数上。
对于求$[1,n]$区间所有数的欧拉函数值的和，可以在线性筛选质数的算法上进一步修改，在每次筛选时同时计算$\phi$值可以达到$O(n)$的时间复杂度。
思路：
对于质数来说，其欧拉函数值为$n-1$。
在线性筛选中，得到的合数都是以$primes[j] \cdot i$的形式给出的。

  1. 当$primes[j]$是$i$的质因数时，有
    $$
    \phi(primes[j]\cdot i)
    $$
    $$=
    primes[j]\cdot i(1-1/p_1)(1-1/p_2)…(1-1/p_n)\cdot(1-1/primes[j])
    $$

$$
=primes[j]*\phi(i)
$$
2. 当$primes[j]$不是$i$的质因数时，有
$$
\phi(primes[j]\cdot i)=\phi(i)\cdot(primes[j]-1)
$$

欧拉定理

若$a$与$n$互质，则有$a^{\phi(n)}\equiv 1(mod\ n)$

证明：
设所有和$n$互质的数为$a_1, a_2,a_3,…,a_{\phi(n)}$，因此$aa_a,aa_2,aa_3,…aa_{\phi(n)}$也是和$n$互质的。
由于在$[1,n]$中，只有$\phi(n)$个与$n$互质的数，即$a_i$，当$aa_i$模上$n$后也与$n$互质且也在$[1,n]$范围之内，且不相等，因此${a_i}$和${aa_i}$是两个一一对应的集合，且${a_i}$与${aa_i\ mod\ n}$是两个相等集合。
因此有
$$
a_1a_2…a_{\phi(n)}\equiv a^{\phi(n)}a_1a_2…a_{\phi(n)}\ mod\ n
$$
证毕。

当$n$为质数时，有
$$
a^{n-1}\equiv 1\ mod\ n
$$

快速幂

快速求出$a^k\ mod\ p$，时间复杂度能达到$O(\log k)$。
基本思路：将$k$拆成用2的次方数之和，然后算出$a$的某次方模$p$的值，再相乘即可。
实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int main() {
    
    int n;
    scanf("%d", &n);
    while(n--) {
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        long long int res = 1, temp = a;
        while(b > 0) {
            if((b & 1) == 1) {
                res = (res * temp) % p;
            }
            b >>= 1;
            temp = (temp * temp) % p;
        }
        
        printf("%lld\n", res);
    }
    
    return 0;
}

乘法逆元

乘法逆元定义：

若整数 $b$，$m$互质，并且对于任意的整数 $a$，如果满足 $b|a$，则存在一个整数 $x$，使得 $a/b≡a×x(mod\ m)$，则称 $x$ 为 $b$ 的模 $m$ 乘法逆元，记为$b^{−1}(mod\ m)$。
$b$ 存在乘法逆元的充要条件是$b$与模数$m$互质。当模数$m$为质数时，$b^{m−2}$即为$b$的乘法逆元。

证明：
IMG_2047.PNG

实现代码（该题限制了$p$一定是质数所以可以这么写）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
int main() {
    
    int n;
    scanf("%d", &n);
    while(n--) {
        int a, b, p;
        scanf("%d%d", &a, &p);
        long long int res = 1, temp = a;
        b = p-2;
        while(b > 0) {
            if((b & 1) == 1) {
                res = (res * temp) % p;
            }
            b >>= 1;
            temp = (temp * temp) % p;
        }
        if(a % p)
            printf("%lld\n", res);
        else
            printf("impossible\n");
    }
    
    return 0;
}

扩展欧几里得算法

裴蜀定理
有一对正整数$a$，$b$，那么一定存在整数$x$和$y$，使得
$$
ax+by=gcd(a,b)
$$

属于是开始复习离散数学内容了（推公式可太难受了）…
在具体实现时，我们可以思考得出$x$、$y$的具体步骤：首先需要通过欧几里得算法正向求到$b= 0$，然后使用再反向推导求出每一步骤的$x$和$y$，因此在实现过程中需要使用递归来求$gcd$，然后在求出当前的$gcd$后在每个函数返回之前求出$x$和$y$。
设这一次有：
$$
ax+by=gcd(a,b)
$$
上一次计算时有：
$$
bx’+(a-a/b\cdot b)y’=gcd(a,b)
=ay’+b(x’-a/b\cdot y’)
$$

Float Point Exception: 除数为0时会报该错。

直接给出代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
int extgcd(int a, int b, int &x, int& y) {
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    int res = extgcd(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp  - a / b  * y;
    return res;
}
int main() {
    int n;
    scanf("%d", &n);
    int x, y;
    while(n--) {
        int a, b;
        scanf("%d%d", &a, &b);
        bool _s = false;
        if(a < b) {swap(a, b); _s = true;}
        extgcd(a, b, x, y);
        if(_s)
            printf("%d %d\n", y, x);
        else
            printf("%d %d\n", x, y);
    }
    return 0;
}

简单应用——线性同余方程

给定$n$组数据$a_i$,$b_i$,$m_i$，对于每组数求出一个$x_i$，使其满足$a_i×x_i≡b_i(mod\ m_i)$，如果无解则输出 impossible。
$$
\begin{align}
& a\cdot x\equiv b\ (mod\ m) \
& \Leftrightarrow ax\equiv m\cdot k+b \
& \Leftrightarrow ax-mk\equiv b \
& \Leftrightarrow ax+k’m\equiv b
\end{align}
$$
正好可以使用扩展欧几里得方法来求解$x$，同时如果$b$不是$gcd(a,m)$的整数倍时，就无解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL extgcd(LL a, LL b, LL &x, LL& y) {
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    LL res = extgcd(b, a % b, x, y);
    LL temp = x;
    x = y;
    y = temp  - a / b  * y;
    return res;
}
int main() {
    int n;
    scanf("%d", &n);
    LL x, y;
    while(n--) {
        LL a, b, m;
        scanf("%lld%lld%lld", &a, &b, &m);
        bool _s = false;
        if(a < m) {swap(a, m); _s = true;}
        LL res = extgcd(a, m, x, y);
        if(b % res != 0) {
            printf("impossible\n");
            continue;
        }
        if(_s)
            swap(x, y);
        if(_s) {
            x = (x * (b / res)) % a;
        } else {
            x = (x * (b / res)) % m;
        }
        printf("%lld\n", x);
    }
    return 0;
}

中国剩余定理

有两两互质的数$m_1,m_2,m_3,…,m_k$，则对于每个数有
$$
x\equiv a_i\ (mod\ m_i)
$$
其中，$M=m_1m_2…m_k$，$M_i=\frac{M}{m_i}$，用$M_i^{-1}$表示$M_i$模$m_i$的逆，因此
$$
x=a_1M_1M_1^{-1}+a_2M_2M_2^{-1}+…+a_kM_kM_k^{-1}
$$
证明请参考离散数学课本…

高斯消元

可以在$O(n^3)$的时间复杂度内计算$n$个变量的多元一维线性方程组。
解会有三种情况：

  1. 有唯一解——可以化成完美阶梯型
  2. 无穷多组解——不是完美阶梯型，存在0=0的方程
  3. 无解——左边没有未知数，右边非零

对于一个系数矩阵来说，可以对其进行三种基本操作：

  1. 把某一行乘上一个非零数
  2. 交换某两行
  3. 把某行若干倍加到另一行上

然后把系数矩阵转化成上三角形即可。
实现代码如下：
值得注意的是，double类型的-0和0是完全不同的，但事实上应该不能输出-0.0。因此，需要使用特判来去掉所有的负0double值。
double类型不能用abs，abs专用于int型，对于浮点数应该使用fabs。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
const int N = 102;
double m[N][N];
double res[N];
int n;
const double eps = 1e-8;
int gauss() {
    for(int i = 1; i <= n; ++i) {
        double temp_max = 0.0;
        int temp_index = 0;
        for(int k = i; k <= n; ++k) {
            if(fabs(m[k][i]) > temp_max) {
                temp_max = fabs(m[k][i]), temp_index = k;
            }
        }
        if(fabs(m[temp_index][i]) < eps && fabs(m[temp_index][n+1]) < eps) {
            return 1;
        } else if(fabs(m[temp_index][i]) < eps && fabs(m[temp_index][n+1] > eps)){
            return 2;
        }
        // start to swap line i and line temp_index
        for(int k = 1; k <= n + 1; ++k) swap(m[temp_index][k], m[i][k]);
        double f = m[i][i];
        for(int k = i; k <= n + 1; ++k) m[i][k] /= f;
        for(int k = i + 1; k <= n; ++k) {
            double f = m[k][i] / m[i][i];
            for(int j = i; j <= n + 1; ++j) {
                m[k][j] -= f * m[i][j];
            }
        }
    }
    
    for(int i = n; i >= 1; --i) {
        if(fabs(m[i][i]) < eps && fabs(m[i][n+1]) < eps) {
            printf("Infinite group solutions");
            return 0;
        }
        if(fabs(m[i][i]) < eps && m[i][n+1] != 0) {
            printf("No solution");
            return 0;
        }
        res[i] = m[i][n+1] / m[i][i];
        for(int j = i - 1; j >= 1; --j) {
            double f = m[j][i] / m[i][i];
            m[j][i] = 0.0;
            m[j][n+1] -= m[i][n+1] * f;
        }
    }
    
    return 0;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n + 1; ++j) {
            scanf("%lf", &m[i][j]);
        }
    }
    int ret = gauss();
    if(ret == 1) {
        printf("Infinite group solutions");
    } else if(ret == 2) {
        printf("No solution");
    } else {
        for(int i = 1; i <= n; ++i) {
            if(fabs(res[i]) < eps) res[i] = 0;
            printf("%.2lf\n", res[i]);
            
        }
    }
    
    
    return 0;
}

组合计数

$$
C_a^b=\frac{a!}{b!(a-b)!}
$$

$$
C_a^b=C_{a-1}^b+C_{a-1}^{b-1}
$$
理解：首先在$a$个物体中挑选一个物体，那么挑选b个物体的结果就分为两种情况：

  1. 包含这个物体，那么个数是$C_{a-1}^{b-1}$
  2. 不包含这个物体，那么个数是$C_{a-1}^b$

与处理思路：
预处理出$C_a^b$的值、或预处理出阶乘的值
如果要预处理阶乘的值，需要注意的是两个数除数的模不等于两数分别模完之后再除。因此还需要求出逆元，那么除数模就变成了一个数乘除数的逆元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
const int N = 2001;
typedef long long LL;
const int mod = 1e9+7;
LL C[N][N];
int main() {

    int n;
    scanf("%d", &n);
    for(int i = 0; i < N; ++i) C[i][0] = 1;
    for(int i = 1; i < N; ++i) C[i][1] = i;
    // for(int i = 1; i <= n; ++i) C[0][i] = 1;
    for(int i = 1; i < N; ++i) {
        for(int j = 2; j < N; ++j) {
            C[i][j] = (C[i-1][j-1]+C[i-1][j]) % mod;
        }
    }
    while(n--) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", C[a][b]);
    }

    return 0;
}

卢卡斯定理

$$
C_a^b=C_{a\ mod\ p}^{b\ mod\ p}\cdot C_{a/p}^{b/p}\ (mod\ p)
$$
该算法适用于求$a$，$b$都是非常大数的组合数，并且求的组合数数量是非常小的情形。
在实际运算时，可以先预处理求出$a$至$b$的所有组合数，然后进行递归求解。
实例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100001;
LL qmi(int a, int b, int p) {
    LL res = 1, temp = a;
    while(b > 0) {
        if(b & 1) {
            res = (LL) res * temp % p;
        }
        b >>= 1;
        temp = temp * temp % p;
    }
    return res;
}

LL C(int a, int b, int p) {
    if(a < b) return 0;
    LL 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) % p;
    }
    return res;
}

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

int main() {
    int n;
    scanf("%d", &n);

    while(n--) {
        LL a, b, p;
        scanf("%lld%lld%lld", &a, &b, &p);
        printf("%lld\n", lucas(a, b, p));
    }
    return 0;
}

当组合数需要高精度，即不求余数，而是求完整的结果时，可以使用求每个数（$a!$,$(a-b)!$和$b!$）表示成每个质数的次方，这样再使用大数乘法去求解即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
const int N = 5001;
int primes[N], cnt;
bool st[N];
int sum[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[i * primes[j]] = true;
            if(primes[j] % i == 0) break;
        }
    }
}

int cal_sum(int a, int p) {
    int times = 0;
    for(int k = 2; k <= a; ++k) {
        int m = k;
        while(m > 1 && m % p == 0) {
            times++;
            m /= p;
        }
    }

    return times;
}

vector<int> mul(vector<int> a, int b) {
    vector<int> res;
    int temp = 0;
    for(int i = 0; i < a.size(); ++i) {
        res.push_back((temp + a[i] * b) % 10);
        temp = (temp + a[i] * b) / 10;
    }
    while(temp > 0) {
        res.push_back(temp % 10);
        temp /= 10;
    }
    return res;
}

int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    get_primes(a);
    if(b > a) {
        printf("0");
        return 0;
    }
    vector<int> res{1};
    for(int i = 0; i < cnt; ++i) {
        int times = cal_sum(a, primes[i]) - cal_sum(b, primes[i]) - cal_sum(a-b, primes[i]);
        for(int j = 0; j < times; ++j) {
            res = mul(res, primes[i]);
        }
    }
    for(int i = res.size() - 1; i >= 0; --i) {
        printf("%d", res[i]);
    }
    return 0;
}

Catalan数

$$
C_{2n}^n-C_{2n}^{n-1}=\frac{C_{2n}^n}{n+1}
$$
该公式适用于非常多的问题…但是何时使用Catalan数仍然是个谜…
记得只要是分母的都是需要使用小费马定理的…
题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
typedef long long LL;

LL qmi(int a, int k, int p) {
    LL res = 1, temp = a;
    while(k > 0) {
        if(k & 1) res = (LL)res * temp % p;
        k >>= 1;
        temp = (LL)temp * temp % p;
    }
    return res;
}

int catalan(int n) {
    LL res = 1;
    for(int i = 1, j = n << 1; i <= n; ++i, --j) {
        res = (LL) res * j % mod;
        res = (LL) res * qmi(i, mod - 2, mod) % mod;
    }
    return (int) res * qmi(n + 1, mod - 2, mod) % mod;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d", catalan(n));
    return 0;
}

容斥原理

$$
1-2+3-4+5-…(-1)^{n-1}\cdot n
$$

$$
\begin{aligned}
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |S_1\cup S_2\cup S_3| \
& =|S_1|+|S_2|+|S_3|-|S1\cap S_2|-|S_2\cap S_3|-|S_1\cap S_3|+|S_1\cap S_2\cap S_3|
\end{aligned}
$$
由于
$$
C_n^0+C_n^1+C_n^2+C_n^3+…+C_n^n=2^n
$$
因此时间复杂度应该是$O(n^2)$。
$$
C_n^1-C_n^2+C_n^3-…+(-1)^{n-1}C_n^n=1
$$
原题链接
给定一个整数$n$和$m$个不同的质数$p_1,p_2,…,p_m$。
请你求出$1∼n$中能被$p_1,p_2,…,p_m$中的至少一个数整除的整数有多少个。
可以看下$n$的取值范围，暴力肯定是无法做到的，所以一定要使用容斥原理。
怎么实现多个集合的并集呢？一般使用位运算来实现（因为递归会消耗太多栈资源）。
注意可能会爆int。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 17;
int p[N];
int main() {
    LL n;
    int m;
    scanf("%lld%d", &n, &m);
    int res = 0;
    for(int i = 0; i < m; ++i) scanf("%d", &p[i]);
    for(int i = 1; i < 1 << m; ++i) {
        int t = 1, cnt = 0;
        for(int k = 0; k < m; ++k) {
            if(i >> k & 1) {
                if((LL)t * p[k] > n) {
                    t = -1;
                    break;
                }
                t = (LL) t * p[k];
                cnt++;
            }
        }
        if(t != -1) {
            if(cnt & 1) {
                res += n / t;
            }
            else {
                res -= n / t;
            }
        }
    }
    printf("%d", res);
    return 0;
}

简单博弈论

公平组合游戏ICG：

  1. 两名玩家交替行动
  2. 每名玩家的行动都相同（五子棋就不是公平组合游戏）
  3. 不能行动的玩家判为负

Nim游戏

给定$n$堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
若：
$$
a_1\ xor\ a_2\ xor\ a_3…\ xor\ a_n=0
$$
说明先手必败，否则先手必胜。
下面需要证明的是：

  1. 如果异或值不为0，那么应该能在一步之内操作，将异或值转为0。
  2. 如果异或值为0，无论怎么拿石子，操作后的异或结果肯定不为0。
    对于1来说，假设所有数的异或结果为$x$，设其二进制表示中1的最高位在第$k$位。说明在$n$个数中必然至少存在一个数$a_i$，其第$k$位二进制数为1。因此有
    $$
    a_i\ xor\ x\ <\ x
    $$
    因此可以在$a_i$堆中拿走$a_i-a_i\ xor\ x$颗石子，因此该堆石子变成了$a_i\ xor\ x$颗石子。
    因此这样操作拿走后异或值就为0。
    2用反证法易证。
    并且由于每次操作都必须要拿石子，总数一直在减少，所以游戏肯定可以结束，因此可以知道0状态就是必胜状态。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int main() {
    int res = 0, n, a;
    scanf("%d", &n);
    while(n--) {
        scanf("%d", &a);
        res ^= a;
    }
    if(res == 0) {
        printf("No");
    } else {
        printf("Yes");
    }
    return 0;
}

SG函数

mex: mex用来表示一个集合中没有出现过的最小自然数
一个状态可能可以转移到很多种状态，
设
$$
SG(终点)=0
$$
每一个状态$x$的SG函数可以表示成如下（设$x$能够出现$y_1,y_2,…,y_k$局面）：
$$
SG(x)=mex{SG(y_1),SG(y_2),…,SG(y_k)}
$$
如果$SG(x)=0$，说明状态$x$是必败状态。如果非零，说明是必胜状态。
任何一种非零状态都可以走到0，但是任意一种0状态是无法再走到0的。
假设有$n$张状态图，起点分别为$x_1,x_2,x_3,…,x_n$，若有
$$
SG(x_1)\ xor\ SG(x_2)\ xor\ SG(x_3)\ xor\ =\ 0
$$
则处于必败状态。
原题链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
const int N = 101, M = 10010;
int n, k;
int s[N], h[N], f[M];

int sg(int x) {
    if(f[x] != -1) return f[x];
    unordered_set<int> S;
    for(int i = 0; i < k; ++i) {
        if(x >= s[i]) S.insert(sg(x-s[i]));
    }
    for(int i = 0; ; ++i)
        if(S.count(i) == 0) 
            return f[x] = i;
}

int main() {
    scanf("%d", &k);
    for(int i = 0; i < k; ++i) scanf("%d", &s[i]);
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%d", &h[i]);
    int res = 0;
    memset(f, 0xff, sizeof f);
    for(int i = 0; i < n; ++i) {
        res ^= sg(h[i]);
    }
    if(res == 0) printf("No");
    else printf("Yes");
    return 0;
}

稍微思考一下可以知道，SG函数适用的场景实际上是Nim游戏的普遍解法，因为之前Nim游戏是能从任意堆拿随便多个，实际上上一题是固定多个，如果将固定多个变为随机多个，也就是$S$集合为无穷，就可以转化成一个简单的Nim游戏。关于每个堆中SG的值也可以通过画图发现，$SG(x)=x$，也与Nim解法相对应。