数学知识

质数

质数的定义：

在大于1的整数中，如果只包含1和本身这两个约束，就被称为质数，或者素数

注意0、1不属于质数，也不属于合数。（定义从2开始）

应用

  • 质数的判定：试除法 $ O ( \sqrt{n} )$

  • 分解质因数：试除法 $ O ( \sqrt{n} )$（实际运行时$ O ( log n ) $~$ O ( \sqrt{n} )$）

  • 筛质数：

    1. 朴素筛法
    2. 埃氏筛法
    3. 线性筛法

质数的判定——试除法

前置知识：

  • 质数是指在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数的自然数

算法分析：

暴力做法：枚举约数，判断是否只有1和自己本身。

优化：约数成对出现，只用枚举每对较小的一个约数

如果在 $2\sim n - 1$ 中存在 $n$ 的约数，不妨设为 $k$，即 $n\bmod k = 0$，那么由 $k\cdot \dfrac{n}{k} = n$ 可知，$\dfrac{n}{k}$ 也是 $n$ 的一个约数，且 $k$ 和 $\dfrac{n}{k}$ 中一定满足其中一个小于等于 $\sqrt n$、另一个大于等于 $\sqrt n$。这启发我们，只需要判定 $n$ 能否被 $2, 3, \cdots, \lfloor \sqrt n \rfloor$ 中的一个整除，即可判定 $n$ 是否为素数。时间复杂度为 $O(\sqrt n)$。

AcWing 866. 试除法判定质数

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
// 质数的判定——试除法
#include <iostream>
#include <algorithm>

using namespace std;

int n;

bool is_primes(int x){
    if (x < 2) return false; // 2是最小的质数，如果n小于2，那n肯定就不是质数
    // 从最小的质数2开始枚举到sqrt(n)
    // 约数成对出现，只用枚举每对较小的一个约数
    //  i <= n / i 比 sqrt(n)快，同时相对于i * i <= n可以防止溢出
    for (int i = 2; i <= x / i; ++ i)
        //如果可以被i整除，说明这个数不是质数
        if(x % i == 0)
        	return false;
    return true;
}
int main(){
    cin >> n;
    while (n--){
        int x;
        scanf("%d", &x);
        if(is_primes(x)) puts("Yes");
        else puts("No");
    }
    return 0;
}
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 质数的判定——试除法
def main():
    n = int(input())
    
    def is_primes(x):
        if x < 2: return False
        i = 2
        while i <= x // i: # 注意整除
            if not x % i:
                return False
            i += 1
        return True
    
    for _ in range(n):
        x = int(input())
        print("Yes" if is_primes(x) else "No")
    
if __name__ == "__main__":
    main()

分解质因数——试除法

前置知识

整数分解的唯一性定理

任意一个正整数a都能分解成质数乘积的形式，并且此表示是唯一的
$$
a = P_1{\alpha_1}P_2{\alpha_2} \ldots P_t^{\alpha_t}
$$

  • 质因子：每个合数都可以写成几个质数相乘的形式,这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数

算法分析

一个正整数 $n$ 必然可以写成一个或多个质数的乘积的形式（$1$ 除外），例如 $6 = 2^1 \times 3^1$，$8 = 2^3$，$180 = 2^2 \times 3^2 \times 5^1$，即
$$
n = p_1^{ \alpha_1 } * p_2^{ \alpha_2 } * \ldots * p_k^{ \alpha_k }, \ \ p_1, p_2, \ldots , p_k皆为质数
$$
本题暴力求解是从小到大枚举所有数，寻找n的质因数。

这里需要注意的一个性质是，由于所有正整数$n$由质数的乘积构成，只要我们从小到大枚举时，把当前质因数完全除尽，每当出现 $ n \ % \ i == 0 $ 的情况时，因数i就一定是质数而不是合数（如果不除尽则不一定）

优化：

对于一个正整数 $n$ 来说，如果它存在除 $1$ 和本身之外的因子，那么一定是在 $\sqrt n$ 左右成对出现。而如果将这个结论放在 “质因子” 上面，会得到一个强化结论：对于一个正整数 $n$ 来说，如果它存在 $[2, n]$ 范围内的质因子，要么这些质因子全部小于等于 $\sqrt n$；要么只存在一个大于 $\sqrt n$ 的质因子，而且其余质因子全部小于等于 $\sqrt n$。

因此n中最多只包含一个大于$\sqrt n$ 的质因子，只用枚举小于$\sqrt n$ 的质因子，最后如果剩下一个大于1的数，则其就是最大的一个质因子

算法步骤

1、枚举 $1\sim \sqrt n$ 范围内所有的质数 $p$，判断 $p$ 是否为 $n$ 的因子。

  • 若 $p$ 是 $n$ 的因子，那么就初始化其个数 $s$ 为 $0$，然后只要 $p$ 还是 $n$ 的因子，就让 $n$ 不断除以 $p$，每次令其个数加 $1$，直到 $p$ 不再是 $n$ 的因子为止。

  • 若 $p$ 不是 $n$ 的因子，就直接跳过。

2、若在步骤 $1$ 结束后 $n$ 仍然大于 $1$，说明 $n$ 有且仅有一个大于 $\sqrt n$ 的质因子（有可能是 $n$ 本身），这时需要初始化其个数为 $1$。

时间复杂度分析

由于我们需要枚举 $1\sim \sqrt n$ 范围内所有的数并进行判断，这步时间复杂度为 $O(\sqrt n)$，而如果我们枚举到的数是 $n$ 的因子但不是质因子，就需要不断让 $n$ 除以 $p$：while (n % p == 0) n /= p, s ++，这步的时间复杂度可以忽略不计，因为即使是 $2$，最多也只会执行 $31$ 次，并且 int 范围内的数最多只会由 $9$ 个不同的质数组合而成，实际执行的次数非常少，时间复杂度的瓶颈在于枚举范围内的数。

至此，就已经将 $n$ 的质因子全部分解出来了。时间复杂度为 $O(\sqrt 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
29
30
31
32
33
// AcWing 867. 分解质因数
// 试除法
#include <iostream>
#include <algorithm>
using namespace std;

int n;

void divide(int x){
    // 只用枚举1~sqrt(n)范围
    for (int i = 2; i <= x / i; ++ i) 
    // i * i < i * (i+1) < (i+1) * (i+1)
        if (x % i == 0){ // 注意i一定是质数
            int s = 0;
            // k = p1^a1*p1^a2...pn^an, p1,p2...pn皆为质数，对应于i一定是质数
            while(x % i == 0){ 
                x /= i; // 除尽当前质因数
                ++ s; // 统计次数
            }
            printf("%d %d\n", i, s);
        }  
    // n中最多只包含一个大于sqrt(n)的质数，只需最后特判
    if (x > 1) printf("%d %d\n", x, 1);
    puts("");
}
int main(){
    scanf("%d", &n);
    while(n --){
        int x;
        scanf("%d", &x);
        divide(x);
    }
}
Python
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
# AcWing 867. 分解质因数
# 试除法
def main():
    n = int(input())
    
    def divide(x):
        i = 2
        while i <= x // i:
            if x % i == 0:
                s = 0
                while x % i == 0:
                    x //= i # 注意整除
                    s += 1
                print("{:d} {:d}".format(i, s))
            i += 1
        if x > 1:
            print("{:d} {:d}".format(x, 1))
        print()
            
    for _ in range(n):
        x = int(input())
        divide(x)
        
if __name__ == "__main__":
    main()

筛质数

前置知识：

  • 自然数按因数的个数分：质数、合数、$0$、$1$ 四类

  • 最小的质数是 $2$，最小的合数是 $4$，连续的两个质数是 $2$、$3$

  • 每个合数都可以由几个质数相乘得到，即合数等于质数之积，质数相乘一定得到合数

  • 除了 $2$ 和 $5$，其余质数的个位都是 $1、 3、 7、 9$

  • 质数定理：当 $n \rightarrow \infty$ 时，$1\sim n$ 中的质数个数为 $\dfrac{n}{\ln n}$。

常用筛法：

1、暴力筛 $O(n\sqrt n)$

通过用判断素数的函数来枚举每一数加入到素数表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
int primes[N], cnt;
bool is_primes(int n){
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i ++ )
        if (n % i == 0)
            return false;
    return true;
}

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

时间复杂度分析：

遍历 $O(n)$，素数判断最坏 $O(\sqrt n)$，总复杂度为 $O(n\sqrt n)$。

2、朴素筛 $O(n\log n)$

任何整数 $x$ 的倍数 $2x, 3x, \cdots$ 都不可能是素数。我们可以从 $2$ 往后扫描，将当前数的所有倍数全部筛掉，剩下没有被筛掉的数就是质数。

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

时间复杂度分析：

当 $i = 2$ 时，第二层循环共循环了 $\dfrac{n}{2}$ 次，$i = 3$ 时循环了 $\dfrac{n}{3}$ 次，$\cdots$，总共循环了：
$$
\dfrac{n}{2} + \dfrac{n}{3} + \cdots + \dfrac{n}{n} = n(\dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n})
$$
其中 $\dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n}$ 为调和级数，当 $n \rightarrow \infty$ 时，有：$\sum\limits_{k=1}^{n} \dfrac{1}{k} = \ln n + \gamma$，并且 $\gamma$ 为欧拉常数（$\text{Euler Constant}$），约为 $0.577215664\ldots$ 故时间复杂度：
$$
n(\dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n})\approx n\ln n \approx n\log n
$$
即 $O(n\log n)$。

3、 埃拉托斯特尼（埃氏）筛 $O(n\log \log n)$

对上面的朴素筛法进行优化，我们发现并不需要将每个数的倍数都筛去，我们可以只把所有质数的倍数筛去。

若按照之前的筛法筛去一个整数的所有倍数，我们最终会留下一些质数，以 $p$ 为例，说明 $p$ 不是 $2\sim p - 1$ 内任何一个数的倍数，我们并不需要将 $2\sim p - 1$ 内所有的数依次枚举一遍，只要将其中的质数枚举一遍即可，因为合数等于质数之积。

1
2
3
4
5
6
7
8
void get_primes(int n){
    for (int i = 2; i <= n; i ++ )
        if (!st[i]){
            primes[cnt ++ ] = i;
            for (int j = i + i; j <= n; j += i ) st[j] = true;
        //  for (LL j = (LL)i * i; j <= n; j += i ) st[j] = true;
        }
}

这里有个优化，$j$ 可以从 $i\cdot i$ 开始枚举，因为 $i\cdot (2\sim i - 1)$ 已经被 $2\sim i - 1$ 筛去了。但由于数据范围限制，这样会使得 $i\cdot i$ 可能会爆 int，因此要开 long long。

时间复杂度分析：

由于我们只用筛去 $2\sim n - 1$ 中的素数倍数即可，故调和级数变为：$\sum\limits_{p\leq n} \dfrac{1}{p}$，其中 $p$ 为质数。当 $n$ 趋于无穷时，有：

$$
M = \lim_{n\to \infty} \left (\sum\limits_{p\leq n} \dfrac{1}{p} - \ln(\ln(n))\right) = \gamma + \sum\limits_p \left [\ln \left(1 - \dfrac{1}{p} \right) + \dfrac{1}{p} \right]
$$

其中，$M$ 为 $\text{Meissel-Mertens}$ 常数，也称 $\text{Mertens}$ 常数或质数倒数和常数，数值约为 $0.261497\ldots$

所以当 $n\rightarrow \infty$ 时，$ n\cdot \sum\limits_{p\leq n} \dfrac{1}{p} \approx n\ln(\ln n) $，即为 $O(n\log \log n)$。

4、 线性（欧拉）筛 $O(n)$

埃氏筛存在一个缺陷，即对于一个合数，可能会被筛多次，例如 $30 = 2\times 15 = 5\times 6\ldots$，我们改用其最小质因子去筛掉这个合数，就可以保证他只会被筛一次。

我们从小到大枚举所有质因子 primes[j]。

1、当出现 i % primes[j] == 0 时，primes[j] 一定是 $i$ 的最小质因子，因此也一定是 primes[j] * i 的最小质因子。

2、当出现 i % primes[j] != 0 时，说明我们还尚未枚举到 $i$ 的任何一个质因子，也就表示 primes[j] 小于 $i$ 的任何一个质因子，这时 primes[j] 就一定是 primes[j] * i 的最小质因子。

可以发现无论如何，primes[j] 都一定是 primes[j] * i 的最小质因子，并且由于所要筛的质数在 $2\sim n$ 之间，因此合数最大为 $n$，故 primes[j] * i 只需枚举到 $n$ 即可，但由于 primes[j] * i 可能会溢出整数范围，故改成 primes[j] <= n / i 的形式。

1
2
3
4
5
6
7
8
9
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; // primes[j] 一定是 i 的最小质因子 
        }
    }
}

时间复杂度分析：

$2\sim n$ 中，任何一个合数都会被筛去，而且仅用最小质因子去筛，每个合数都有且仅有一个最小质因子，故每个合数只会被筛一次，所以时间复杂度为 $O(n)$。

AcWing 868. 筛质数

朴素筛法

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
// AcWing 868. 筛质数 
// 朴素筛法
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;

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

void get_primes(int n){
    for (int i = 2; i <= n; ++ i){
        if (!st[i]){
            primes[cnt++] = i;
        }
        for (int j = i + i; j <= n; j += i) st[j] = true;
    }
}
int main(){
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 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
// AcWing 868. 筛质数 
// 埃氏筛法
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1000010;

int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
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;
        }
    }
}
int main(){
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 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
32
33
34
35
// AcWing 868. 筛质数 
// 线性筛法求素数
// 核心方法是使用primes[j]筛掉primes[j] * i
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1000010;

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

void get_primes(int n){
    // 枚举所有数
    for(int i = 2; i <= n; ++ i){
        if (!st[i]) primes[cnt++] = i; // 没被筛掉说明是质数
        // 使用当前所有质数进行筛选，且每个数只会由其最小质因子筛掉
        // 即使用primes[j]筛掉primes[j] * i
        // primes[j] * i > n 时不再具有筛选意义
        for (int j = 0; primes[j] <= n / i; ++ j){
            st[primes[j] * i] = true;// n只会被最小质因子筛掉
            //primes[j]一定是primes[j] * i的最小质因子。
            // 到i的最小质因子截止
            if (i % primes[j] == 0) break; // primes[j]一定是i的最小质因子
            // 注意循环一定会停止，i为质数时，则primes[j]最后一个等于i，会break；i不为质数则一定存在primes[j]使break
        }
    }
}
int main(){
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}
Python
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
# AcWing 868. 筛质数 
# 线性筛法求素数
# 核心方法是使用primes[j]筛掉primes[j] * i
def main():
    n = int(input())
    primes = [0] * (n + 1)
    st = [False] * (n + 1)

    def get_primes(n):
        cnt = 0
        for i in range(2, n + 1):
            if not st[i]:
                primes[cnt] = i
                cnt += 1
            j = 0
            while primes[j] <= n // i:
                st[primes[j] * i] = True
                j += 1
                if i % primes[j - 1] == 0:
                    break

        print(cnt)
        
    get_primes(n)
    
if __name__ == "__main__":
    main()

约数

应用

  1. 试除法求一个数的所有约数

  2. 约数个数

  3. 约数之和

试除法求所有约数

对于一个正整数 $n$ 来说，如果它存在除 $1$ 和本身之外的因子，那么一定是在 $\sqrt n$ 左右成对出现。所以我们在求一个整数 $n$ 的所有约数时，只需要求出较小的那一个约数即可。

例如对于 $3 \times 4 = 12,\ 4 \times 3 = 12$，两种情况是等价的，一个公式能枚举出两个约数。

算法步骤：

对于一个整数 $n$，它的任意两个约数 $a,\ b$ 满足 $a \leq \sqrt n,\ \ b \geq \sqrt n$。

所以我们在枚举时，只需要枚举 $1\sim \sqrt n$，保存较小的那个约数 $a$ 和对应的另一个约数 $\dfrac{x}{a}$，注意需要特判一下两个约数是否相等**（因为有可能是开方）。

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
#include <iostream>
#include <algorithm>

using namespace std;

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

int main(){
    int n;
    cin >> n;
    while(n--){
        int x;
        cin >> x;
        auto res = get_divisors(x);
        for (auto t : res) cout << t << ' ';
        cout << endl;
    }
    return 0;
}

约数个数

算法分析：

如果要求一个正整数 $n$ 的因子个数，只需要对其进行质因子分解，得到各质因子的个数分别为 $e_1, e_2, \ldots, e_k$，于是 $n$ 的因子个数就是 $(e_1 + 1)\cdot (e_2 + 1)\cdot \ldots \cdot (e_k + 1)$。

原因是，对于每个质因子 $p_i$，都可以选择其出现 $0$ 次、$1$ 次、$\cdots$、$e_i$ 次，共有 $e_i + 1$ 种可能，组合起来就是答案。

求约数个数的公式：
$$
如果 N = p_1^{c_1} * p_2^{c_2} * … *p_k^{c_k},\\约数个数=(c_1 + 1) * (c_2 + 1) * … * (c_k + 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
26
27
28
29
30
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main(){
    int n;
    cin >> n;
    unordered_map<int, int> primes;// 存储每个质因子的次数
    // 使用数值直接存储浪费空间，使用map存储
    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 prime : primes) res = res * (prime.second + 1) % mod;
    // map容器的迭代器里面有first()和second()，first()相当于健的迭代器，second()相当于值的迭代器
    // 取模时利用性质: a*b mod n = (a mod n) * (b mod n) mod n = (a mod n) * b mod n;
    // 这里分别处理每个正整数即可，不需要先乘在一起
    cout << res << endl;
    return 0;
}

约数之和

求约数之和的公式：
$$
如果 N = p_1^{c_1} * p_2^{c_2} * … *p_k^{c_k},\\
约数之和=(p_1^0 + p_1^1 + … + p_1^{c_1}) * … * (p_k^0 + p_k^1 + … + p_k^{c_k})
$$

算法分析：对于任意一个自然数 $n$，可以将其分解为：$$n = p_1^{e_1}\cdot p_2^{e_2}\cdot p_3^{e_3}\cdot \ldots \cdot p_k^{e_k}$$

其中 $p_i$ 表示质因子，$e_i$ 表示 $p_i$ 的指数（即该质因子的个数），则 $n$ 的约数个为: $$(e_1 +1)\cdot (e_2 + 1)\cdot (e_3 + 1)\cdot \ldots \cdot (e_k + 1)$$

其约数之和为：

$$(1 + p_1^1 + p_1^2 + \cdots + p_1^{e_1})\cdot (1 + p_2^1 + p_2^2 + \cdots + p_2^{e_2})\cdot \ldots \cdot (1 + p_k^1 + p_k^2 + \cdots + p_k^{e_k})$$

等比数列求和公式：
$$
S_n= \frac{a_1(1-q^n)}{(1-q)}
$$

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 <iostream>
#include <algorithm>
#include <unodered_map>

using namespace std;

const int mod = 1e9 + 7;

typedef long long LL;

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 prime : primes){
        int p = prime.first, a = prime.second;
        LL t = 1;
        // t = 1 --> t*p + 1 = p + 1
        while (a--) t = (t * p + 1) % mod; // 利用递推式求和
        // a * b % p = (a % p) * b % p = (a % p) * (b % p) % p
        // (a + b) % p = (a % p + b % p) % p 
        res = res * t % mod;
    }
    cout << res << endl;

    return 0;
}

欧几里得算法(辗转相除法)

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)

$O(logn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>

using namepsace std;

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a; // 递归写法
}

int main(){
    int n;
    scanf("%d", &n);
    while(n--){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }
    return 0;
}

最小公倍数 = 两数相乘 / 最大公约数

1
2
3
4
5
6
7
8
9
10
# 求两个数的最大公约数
# 也可以调库 from math import gcd
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

# 求两个数的最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

公式法求欧拉函数

欧拉函数：在数论，对正整数n，欧拉函数是小于等于n的正整数中与n互质的数的数目。互质：互质是公约数只有1的两个整数，叫做互质整数。公约数只有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 <iostream>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin >> n;
    while(n--){
        int a;
        cin >> a;
        int res = a;
        // 试除法分解质因数
        // 欧拉公式fa(n) = N * p1 * (p1 - 1) * p2 * (p2 - 1)... * pn * (pn -1)
        for (int i = 2; i <= a / i; ++i) //
            if (a % i == 0){
                res = res / i * (i - 1);
                while (a % i == 0) a /= i;
            }
        if (a > 1) res = res / a * (a - 1);

        cout << res << endl;
    }
    return 0;
}

线性筛法求1~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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1000010;

typedef long long LL;

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

LL get_eulers(int n){
    euler[1] = 1;
    for (int i = 2; i <= n; ++i){
        if (!st[i]){ // 是否为质数
            primes[cnt++] = i;
            euler[i] = i - 1; // 质数p的欧拉函数值为p-1
        }
        // 线性筛法 关键在于利用了质数的欧拉函数的特性 
        for (int j = 0; primes[j] <= n / i; ++j){
            int t = primes[j] * i;
            // 求质因子的i倍的欧拉函数值，且primes[j]必须是primes[j] * i 的最小质因子
            st[t] = true;
            if (i % primes[j] == 0){// primes[j]是i的最小质因子
                euler[t] = euler[i] * primes[j];
                break;
            }
            // primes[j]不是i的最小质因子
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
    LL res = 0;
    for (int i = 1; i<= n; ++i) res += euler[i];
    return res;
}

int main(){
    LL n;
    cin >> n;
    cout << get_eulers(n) << endl;
    return 0;
}

威尔逊定理

若p为质数，则

p|(p-1)!+1

欧拉定理和费马小定理

欧拉定理：若a与n互质，则
$$
a^{\phi(n)} \equiv 1\ (mod \ n)
$$
费马小定理：若p是质数，则对于任意整数a，有
$$
a^{p-1} \equiv 1\ ( mod \ p )
$$

欧拉定理的推论

  • 若正整数a，n互质，那么对于任意正整数b，有
    $$
    ab≡a{b\ mod\ \phi (n)}\ (mod\ n)
    $$

  • 有针对a，p互质的推论，不过我们直接说扩展的。即p为任意数。
    $$
    if ( b < \phi(p) ), a^b = a^b\ (mod \ p)
    $$
    $$
    if ( b >= \phi(p) ), a^b = a^{b, mod , \phi (p) \ +\ \phi(p)}\ (mod \ p )
    $$

求逆元：

当p为质数时，可以使用费马小定理和快速幂求逆元；当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
27
28
29
// 快速幂求逆元
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
// a^k % p 快速幂
int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if (k & 1) res = (LL) res * a % p;
        k >>= 1;
        a = (LL) a * a % p;
    }
    return res;
}

int main(){
    int n;
    scanf("%d", &n);
    while (n--){
        int a, p;
        scanf("%d\n", &a, &p);

        int res = qmi(a, p-2, p);// p-2=0时比较特殊，一定返回1
        if (a % p) printf("%d\n", res);// 要判断a与p是否互质
        else puts("impossible");
    }
    return 0;
}

快速幂

在$O(logk)$复杂度内快速求出$ a^k \ mod \ p $的结果($ 1 \leq a, p, k \leq 10^9$)

将k用2的幂表示，预处理出$a{2i}$

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 <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

// a^k % p
int qmi(int a, int k, int p){
    int res = 1 % p;
    while(k){
        if (k & 1) res = (LL)res * a % p; // 截取k的二进制表示中的最后一位
        // 按位与运算有两种典型用法，一是取一个位串信息的某几位，如以下代码截取x的最低7位：x & 0177。二是让某变量保留某几位，其余位置0，如以下代码让x只保留最低6位：x = x & 077。以上用法都先要设计好一个常数，该常数只有需要的位是1，不需要的位是0。用它与指定的位串信息按位与。
        k >>= 1; // k右移除2
        //  右移运算将一个位串信息向右移指定的位，右端移出的位的信息被丢弃。例如12>>2,结果为3。与左移相反，对于小整数，每右移1位，相当于除以2
        a = (LL)a * a % p;
    }
    return res;
}

int main(){
    int n;
    cin >> n;
    while(n--){
        int a, k , p;
        scanf("%d%d%d", &a, &k, &p);
        printf("%d", qmi(a, k ,p));
    }
    return 0;
}

裴蜀定理

对于任意正整数a,b，一定存在正整数x,y，使得ax + by = (a,b)，且其为a和b能表示出的最小的正整数。(a,b)表示a和b的最大公约数。x,y不唯一。

扩展欧几里得算法

由(a,b) = (b,a % b)，则ap + bq = by + (a mod b)x = (a, b)。又$a \ mod\ b = a - \lfloor \frac{a}{b}\rfloor * b$，得公式：
$$ax + b(y - \lfloor\frac{a}{b}\rfloor * x) = (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
// 扩展欧几里得算法
#include <iostream>

using namespace std;

// 使用递归法
int exgcd(int a, int b, int &x, int &y){
    if(!b) // 边界：b=0时，可以找到一组特解：x = 1, y = 0
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x); // 递归求最大公约数
    y -= a / b * x;// 利用公式更新y
    return d;
}

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

    while (n--){
        int a, b ,x, y;
        scanf("%d%d", &a, &b);
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }
}

应用：求解线性同余方程

线性同余方程：已知$a * x\equiv b \ (mod \ m) $，求x

该方程等价于存在整数y，使得$a * x = m * y + b$，即存在整除y’，使得$ax+my’= 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
// 扩展欧几里得算法求解线性同余方程
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

// 扩展欧几里得算法
int exgcd(int a, int b, int &x, int &y){
    if(!b){
        x = 1, y = 1;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a/ b * x;
    return d; 
}

int main(){
    int n;
    scanf("%d", &n);
    while(n--){
        int a, b ,x, y;
        scanf("%d%d%d", &a, &b, &m);
        int d = exgcd(a, m, x, y);
        if (b % d) puts("impossible");
        else printf("%d\n",(LL)x * (b / d) % m); // 注意系数的变化
    }
    return 0;
}

中国剩余定理

中国剩余定理

对于一元线性同余方程组，不互为质数时要用扩展欧几里得算法

对于方程组：
$$
\begin{cases}
x = k_1 * a_1 + m_1 \\
x = k_2 * a_2 + m_2 \\
\end{cases}
$$
首先，可得$k_1 * a_1 + m_1 = k_2 * a_2 + m_2$，即$k_1a_1 - k_2a_2=m_2 - m_1$。由扩展欧几里得算法，其有解等价于$$(a_1,a_2) |m_2-m_1,\ \ (m_2-m_1整除a_1和a_2的最大公约数)$$通解为
$$
\begin{cases}
k_1 = k_1 + k_1 * \frac{a_1}{d} \\
k_2 = k_2 + k_2 * \frac{a_2}{d} \\
\end{cases}
$$

因而整理得
$$
x = a_1k_1 + m_1 + k \frac{a_1 * a_2} {d}
$$
即
$$
x = x_0 + k a,\ \ 其中x_0 = a_1k_1 + m_1, \ a = \frac{a_1 * a_2} {d}
$$

按照以上过程，可以将方程组化为一个方程。此时$x \equiv x_0\ (mod\ a)$，x为最小正整数时，可解得
$$
x = x_0 \ mod\ a
$$

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
// 一元线性同余方程组非互质情况——扩展欧几里得算法
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

// 扩展欧几里得算法
LL exgcd(LL a, LL b, LL &x, LL&y){
    if (!b){
        x = 1, y = 1;
        return a;
    }
    LL d = exgcd(b, a % b , y , x);
    y -= a / b  * x;
    return d;
}

int main(){
    int n;
    cin >> n;
    bool has_answer = true;
    LL a1, m1;

    cin >> a1 >> m1;

    for (int i = 0; i < n - 1; ++ i){
        LL a2, m2;
        cin >> a2 >> m2;

        LL k1, k2;
        LL d = exgcd(a1, a2, k1, k2); // 求出最大公约数
        if ((m2 - m1) % d) // 判断是否可解
        {
            has_answer = false;
            break;
        }
        k1 *= (m2 - m1) / d; // 使k1变为 m2 - m1对应得系数
        LL t = a2 / d; 
        k1 = (k1 % t + t) % t; // 为防止溢出，要使k1最小
        // 注意(a % m + a) % m 得写法可应对负数问题，保证余数为非负
        m1 = a1 * k1 + m1; 
        a1 = abs(a1 / d * a2); // 利用公式
    }
    
    if (has_answer){
        cout << (m1 % a1 + a1) % a1 << endl;
    }
    else puts("-1");
    return 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
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
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;
const double eps = 1e-6;
int n;
double a[N][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]))
            t = i;
        if (fabs(a[t][c]) < eps) continue; // 为0的话就无需处理

        for (int j = c; j <= n; ++j) swap(a[t][j], a[r][j]); // 将绝对值最大的行换到最顶端
        for (int j = n; j >= c; --j) a[r][j] /= a[r][c]; // 将当前行的首位变成1
        for (int i = r + 1; i < n; ++i) // 用当前行将下面所有的列消成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)
                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];
    
    return 0; // 有唯一解
}

int main(){
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n + 1; ++j)
            cin >> a[i][j];
    
    int t = gauss();
    if (t == 0)
    {
        for (int i = 0; i < n; ++ i) 
        {
            if (fabs(a[i][n]) < eps) a[i][n] = 0;
            printf("%.2lf\n", a[i][n]);
        }
    }
    else if (t == 1) puts("Infinite group solutions");
    else puts("No solution");
    return 0;



}



递归法求组合数

利用组合数的性质之递推公式：
$$C^b_a = C^b_{a-1} + C^{b-1}_{a-1}$$
适用范围：$$10万组，1 \leq b \leq a\leq 2000$$

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
#include <iostream>
#include <algorithm>

using namespace std;

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

int c[N][N];

// 先全部暴力递归求出
void init()
{
    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;
            // 注意c[i-1][i]本是不存在的，但这里由于其值为0，且c[i][i]所=c[i-1][i-1]，所以不影响
}

int main(){
    init();
    int n;
    scanf("%d", &n);
    while(n--){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", c[a][b]);
    }
    return 0;
}


通过预处理逆元的方式求组合数——预处理出阶乘

适用范围：
$$
1万，1\leq b \leq 10^5
$$
公式：
$$
C^b_a = fact[a] * infact[a - b] * infact[b]
$$
fact[a] = a! mod 1e9 + 7

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
// 通过预处理逆元的方式求组合数——预处理出阶乘
// 首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]; 如果取模的数是质数，可以用费马小定理求逆元
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 100010, mod = 1e9 + 7;

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

int main(){
    // // 预处理所有阶乘的余数和阶乘逆元的余数
    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;// 费马小定理要求mod为质数
    }
    int n;
    scanf("%d", &n);
    while(n--){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n",(LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
    }
    return 0;
}


Lucas定理求组合数

若p是质数，则对于任意整数 1 <= m <= n，有：
$$
C^b_a\equiv C^{b, mod,p}{a, mod, p} * C^{b/p}{a/p}\ (mod \ p)
$$
适用于p取值范围较大又不太大，适用范围：
$$
10组，1 \leq b \leq a \leq10^{18}, 1\leq 10^5
$$

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
// Lucas定理求组合数
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int p;

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

int C(int a, int b)  // 当a和b都小于p时，通过最基础的求组合数的方法——组合数基本公式求组合数C(a, b)
{
    if (a < b) return 0;

    LL x = 1, y = 1;  // x是分子，y是分母
    for (int i = a, j = 1; j <= b; -- i, ++ j)
    {
        x = (LL)x * i % p; // 求(a - b + 1)!
        y = (LL)y * j % p; // 求b!
    }

    return x * (LL)qmi(y, p - 2) % p;
}

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;
    // b应该小于a，否则值为0.
}

int main(){
    int n;
    cin >> n;
    while (n--)
    {
        LL a, b;
        cin >> a >> b >> p;
        cout << lucas(a, b) << endl;
    }
    return 0;
}



分解质因数法求组合数

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

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
76
77
78
79
80
81
82
83
84
85
// 分解质因数法求组合数 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 5010;

// 分解质因数
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！中的次数
{
    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); // 只保留10的余数
        t /= 10;//上移一位
    }

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

    return c;
}

int main(){
    int a, b;
    cin >> a >> b;

    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]);
    
    for (int i = res.size() - 1;i >= 0; -- i) printf("%d", res[i]);
    puts("");
    return 0;
}


卡特兰数

  • 卡特兰数（英语：Catalan number），又称卡塔兰数、明安图数，是组合数学中一种常出现于各种计数问题中的数列。

  • 卡特兰数有以下公式：
    $$C_{2n}^n + C^{n-1}{2n} = \frac{1}{n+1}C^n{n+1},\quad \ \frac{1}{n+1}C^n_{n+1}即为卡特兰数。$$

  • 卡特兰数$C_n$满足以下递推关系：

  1. $$C_{n + 1} = C_0C_n+C_1C_{n-1}+\cdots+C_nC_0$$

  2. $$(n-3)C_n = \frac{n}{2}(C_3C_{n-1} + C_4C_{n-2}+C_5C_{n-3}+\cdots+C_{n-2}C_4+C_{n-1}C_3)$$

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
// 求卡特兰数
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int mod = 1e9 + 7;

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

int main(){
    int n;
    cin >> n;

// 使用普通的组合数定义公式+逆元求组合数
    int a = 2 * n, b = n;

    int res = 1;

    for (int i = a, j = 1; j <= b; -- i, ++ j)
    {
         res = (LL)res * i  % mod;
         res = (LL)res * qmi(j, mod -2, mod) % mod;
    }
    res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;// 别忘了1/n+1


    cout << res << endl;

    return 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
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
76
77
78
79
80
81
82
83
// 容斥原理
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 20;

int n, m;
int p[N];

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

    int res = 0;
    // 容斥原理公式的$2^n-1$个项对应于$2^n-1$种选法，其中偶数个项的为正，奇数个项的为负
    // 使用位运算进行枚举，把i看成m位的二进制数
    // 1 << m 表示1的二进制左移m位，当其再转换为十进制数时即表示$2^m$，注意这里i从1开始（至少选一项）
    for (int i = 1; i < 1 << m; ++ i){
        int t = 1, cnt = 0;
        // t 表示当前所有质数的乘积
        // cnt 表示当前选法有几个项（对应于几个集合）
        for (int j = 0; j < m; ++ j)
            if (i >> j & 1){ 
            // >>:将一个数的各二进制位右移N位，移到右端的低位被舍弃，对于无符号数，高位补0。
            // i >> j & 1:i的二进制中，从右往左数，取第j+1位上的值
                cnt ++;
                if ((LL)t * p[j] > n)
                {
                    t = -1; // 说明此选法不成立
                    break;
                }
                t *= p[j]; // 对应于该选法中含有p[j]这一项
            }
        if (t != -1){
            // 求倍数个数使用 n / t
            if (cnt % 2) res += n / t;
            else res -= n / t;
            // 由项数就奇偶判断正负，偶数个项的为正，奇数个项的为负
        }
    }
    cout << res << endl;

    return 0;
}


const int N = 20;

int n, m;
int p[N];

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

    int res = 0;
    for (int i = 0; i < 1 << m; ++ i){
        int t  = 1, cnt = 0;
        for (int j = 0; j < m; ++ j)
            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;
        }
    }
    cout << res << endl;
    return 0;
}



博弈论

Nim游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>

using namesapce std;

int main(){
    int n;
    int res = 0;
    scanf("%d", &n);
    while(n--){
        int x;
        scanf("%d", &x);
        res *=x;
    }
    if (res) puts("Yes");
    else puts("No");

    return 0;
}

集合-Nim游戏

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 <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>

isng namespace std;
cosnt int N = 110, M = 10010;
int n, m;
int s[N], f[M];

int sg(int x){
    if (f[x] != -1) return f[x];
    unordered_set<int> S;
    for (itn i = 0; i < m; ++ i)
    {
        int sum = s[i];
        if ( x >= sum) S.insert(sg(x - sum));
    }
    for (int i = 0; ; ++ i)
        if (!S.coutn(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;
}