Skip to content

15 、数论

1、模运算📌

\[ (a+b) \mod m=((a \mod m)+(b\mod m))\mod m\\ \]
\[ (a-b) \mod m=((a \mod m)-(b\mod m)+m)\mod m\\ \]
\[ (a*b) \mod m=((a \mod m)*(b\mod m))\mod m\\ \]

2、快速幂📌

每次折半，自己跟自己乘

\[ 2^{10}=4^{5}=4\times16^{2}=4\times256^{1} \]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
long long fast_pow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b % 2 == 1) {
            ans = ans * a;
        }
        a = a * a;
        b /= 2;
    }
    return ans;
}

3、埃氏筛📌

给定n，求\(2\sim n\) 内所有素数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
const int MAX_N = 1e6 + 10; // 可以根据需要修改这个值
bool is_prime[MAX_N]; // 用来标记素数

void sieve() {
    fill(is_prime, is_prime + MAX_N, true); // 初始化所有数为素数
    is_prime[0] = is_prime[1] = false; // 0和1不是素数

    for (int i = 2; i * i < MAX_N; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAX_N; j += i) {
                is_prime[j] = false; // 将i的倍数标记为非素数
            }
        }
    }
}

4、GCD/LCM📌

GCD📌

  • 手写
\[ gcd(a,b)=gcd(b,a \mod b) \]
1
2
3
int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}
  • 库函数__gcd(a,b)

LCM📌

\[ LCM=\frac{a\times b}{GCD} \]
1
2
3
int lcm(int x, int y) {
    return x / gcd(x, y) * y; // 先除后乘，防止溢出
}

例题📌

e.g.45 [蓝桥杯 2022 省 B] 刷题统计📌

题目描述

小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 \(a\) 道题目，周六和周日每天做 \(b\) 道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于 \(n\) 题?

输入格式

输入一行包含三个整数 \(a, b\) 和 \(n\).

输出格式

输出一个整数代表天数。

样例

样例输入 

1
10 20 99

样例输出 

1
8

提示

对于 \(50 \%\) 的评测用例，\(1 \leq a, b, n \leq 10^{6}\).

对于 \(100 \%\) 的评测用例，\(1 \leq a, b, n \leq 10^{18}\).

蓝桥杯 2022 省赛 B 组 C 题。

 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;
#define int long long
int32_t main() {
    int a, b, n;
    cin >> a >> b >> n;
    int sum = (5 * a) + (2 * b);
    // cout << sum << endl;
    int day=n/sum*7;
    n-=n/sum*sum;   
    for(int i=1;i<=5;i++){
        if(n>0){
            day++;
            n-=a;
        }
    }
    for(int i=1;i<=2;i++){
        if(n>0){
            day++;
            n-=b;
        }
    }

    cout << day << endl;
}

e.g.46 [蓝桥杯 2018 省 A] 倍数问题📌

题目描述

众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你 \(n\) 个数，希望你从这 \(n\) 个数中找到三个数，使得这三个数的和是 \(K\) 的倍数，且这个和最大。数据保证一定有解。

输入格式

从标准输入读入数据。

第一行包括 \(2\) 个正整数表示 \(n\) 和 \(K\)。

第二行 \(n\) 个正整数，代表给定的 \(n\) 个数。

输出格式

输出一行一个整数代表所求的和。

样例

样例输入 

1
2
4 3
1 2 3 4

样例输出 

1
9

提示

【样例解释】

选择 \(2\)、\(3\)、\(4\)。

【数据约定】

对于 \(30\%\) 的数据，\(n \le 100\)。

对于 \(60\%\) 的数据，\(n \le 1000\)。

对于另外 \(20\%\) 的数据，\(K \le 10\)。

对于 \(100\%\) 的数据，\(1 \le n \le 10^5\)，\(1 \le K \le 10^3\)，给定的 \(n\) 个数均不超过 \(10^8\)。

时限 1 秒，256M。蓝桥杯 2018 年第九届省赛。

 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
int n, k, ans;
vector<int> v[N];
bool cmp(int x, int y) {
    return x > y;
}
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        v[x % k].push_back(x);
    }
    for (int i = 0; i < k; i++)
        sort(v[i].begin(), v[i].end(), cmp);
    for (int i = 0; i < k; i++)
        for (int j = 0; j < k; j++) {
            int u = k - i - j;
            if (u < 0)
                u += k;
            if (i == 0 && j == 0)
                u = 0;

            int x, y, z;
            if (v[i].size() == 0)
                continue;
            else
                x = v[i][0];

            if (i == j) {
                if (v[j].size() <= 1)
                    continue;
                else
                    y = v[j][1];
            } else if (v[j].size() == 0)
                continue;
            else
                y = v[j][0];

            if (u == i && u != j) {
                if (v[i].size() <= 1)
                    continue;
                else
                    z = v[i][1];
            } else if (u == j && u != i) {
                if (v[j].size() <= 1)
                    continue;
                else
                    z = v[j][1];
            } else if (i == u && j == u) {
                if (v[u].size() <= 2)
                    continue;
                else
                    z = v[u][2];
            } else if (v[u].size() == 0)
                continue;
            else
                z = v[u][0];

            ans = max(ans, x + y + z);
        }
    cout << ans << endl;
    return 0;
}

e.g.47【模板】快速幂📌

题目描述

给你三个整数 \(a,b,p\)，求 \(a^b \bmod p\)。

输入格式

输入只有一行三个整数，分别代表 \(a,b,p\)。

输出格式

输出一行一个字符串 a^b mod p=s，其中 \(a,b,p\) 分别为题目给定的值， \(s\) 为运算结果。

样例

样例输入 

1
2 10 9

样例输出 

1
2^10 mod 9=7

提示

样例解释

\(2^{10} = 1024\)，\(1024 \bmod 9 = 7\)。

数据规模与约定

对于 \(100\%\) 的数据，保证 \(0\le a,b < 2^{31}\)，\(a+b>0\)，\(2 \leq p \lt 2^{31}\)。

 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;
#define int long long
int a, b, p;
int32_t fast_pow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b % 2 == 1) {
            ans = ans * a % p;
        }
        a = a * a % p;
        b /= 2;
    }
    return ans % p;
}
int32_t main() {

    cin >> a >> b >> p;
    cout << a << '^' << b << " mod " << p << '=' << fast_pow(a, b) << endl;
    return 0;
}

e.g.48 [HNOI2008] 越狱📌

题目描述

监狱有 \(n\) 个房间，每个房间关押一个犯人，有 \(m\) 种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

答案对 \(100,003\) 取模。

输入格式

输入只有一行两个整数，分别代表宗教数 \(m\) 和房间数 \(n\)。

输出格式

输出一行一个整数代表答案。

样例

样例输入 

1
2 3

样例输出 

1
6

提示

样例输入输出 1 解释

状态编号 1 号房间 2 号房间 3 号房间
1 信仰 1 信仰 1 信仰 1
2 信仰 1 信仰 1 信仰 2
3 信仰 1 信仰 2 信仰 2
4 信仰 2 信仰 1 信仰 1
5 信仰 2 信仰 2 信仰 2
6 信仰 2 信仰 2 信仰 1

数据规模与约定

对于 \(100\%\) 的数据，保证 \(1 \le m \le 10^8\)，\(1 \le n \le 10^{12}\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
#define int long long
int m, n, mod = 100003;
// 快速幂
long long fast_pow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) { // 用“&”判断奇偶性
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1; // 右移一位,相当于除以2
    }
    return ans % mod;
}
int32_t main() {
    cin >> m >> n;
    int x = fast_pow(m, n);
    int y = fast_pow(m - 1, n - 1);
    cout << (x - m * y % mod + mod) % mod << endl;
}

e.g.49 [NOIP2002 普及组] 选数📌

题目描述

已知 \(n\) 个整数 \(x_1,x_2,\cdots,x_n\)，以及 \(1\) 个整数 \(k\)（\(k<n\)）。从 \(n\) 个整数中任选 \(k\) 个整数相加，可分别得到一系列的和。例如当 \(n=4\)，\(k=3\)，\(4\) 个整数分别为 \(3,7,12,19\) 时，可得全部的组合与它们的和为：

\(3+7+12=22\)

\(3+7+19=29\)

\(7+12+19=38\)

\(3+12+19=34\)

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：\(3+7+19=29\)。

输入格式

第一行两个空格隔开的整数 \(n,k\)（\(1 \le n \le 20\)，\(k<n\)）。

第二行 \(n\) 个整数，分别为 \(x_1,x_2,\cdots,x_n\)（\(1 \le x_i \le 5\times 10^6\)）。

输出格式

输出一个整数，表示种类数。

样例

样例输入 

1
2
4 3
3 7 12 19

样例输出 

1
1

提示

【题目来源】

NOIP 2002 普及组第二题

 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;
typedef long long ll;
int n, k, ans, a[30];
bool check(int x) {
    if (x <= 1)
        return false;
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0)
            return false;
    }
    return true;
}
void dfs(int u, int s, int sum) {
    if (s == k) {
        if (check(sum))
            ans++;
        return;
    }
    for (int i = u; i <= n; i++)
        dfs(i + 1, s + 1, sum + a[i]);
}
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    dfs(1, 0, 0);
    cout << ans << endl;
    return 0;
}

e.g. 50 [GESP202309 五级] 因数分解📌

题目描述

每个正整数都可以分解成素数的乘积，例如： \(6=2\times 3\)，\(20=2^2\times5\)。

现在，给定一个正整数，请按要求输出它的因数分解式。

输入格式

输入第一行，包含一个正整数 \(N\)。约定 \(2 \le N \le 10^{12}\)。

输出格式

输出一行，为的因数分解式。要求按质因数由小到大排列，乘号用星号 * 表示，且左右各空一格。当且仅当一个素数出现多次时，将它们合并为指数形式，用上箭头 ^ 表示，且左右不空格。

样例

样例输入 

1
6

样例输出 

1
2 * 3

样例

样例输入 

1
20

样例输出 

1
2^2 * 5

样例

样例输入 

1
23

样例输出 

1
23

 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>
#define ll long long
using namespace std;
ll n, cnt;
int main() {
    cin >> n;
    for (ll i = 2; i * i <= n; i++) // 记得开long long，从2开始
    {
        cnt = 0;        // 记录质因数个数
        if (n % i == 0) // 如果i是质因数
        {
            while (n % i == 0) // 一直分解直到无法分解为止
            {
                n /= i;
                cnt++;
            }
            if (cnt == 1)
                cout << i; // 如果只有一个，不用输出指数
            else
                cout << i << '^' << cnt; // 否则输出指数
            if (n > 1)
                cout << " * "; // 如果不是最后一个质因数就输出乘号
        }
    }
    if (n > 1)
        cout << n; // 如果没分解干净就输出剩下的质因数
    return 0;
}

e.g.51 素数密度📌

题目描述

给定 \(L,R\)，请计算区间 \([L,R]\) 中素数的个数。

\(1\leq L\leq R < 2^{31}\)，\(R-L\leq 10^6\)。

输入格式

第一行，两个正整数 \(L\) 和 \(R\)。

输出格式

一行，一个整数，表示区间中素数的个数。

样例

样例输入 

1
2 11

样例输出 

1
5

e.g.52 核桃的数量📌

题目描述

小张是软件项目经理，他带领 \(3\)个开发组。工期紧，今天都在加班呢。为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。他的要求是：

  1. 各组的核桃数量必须相同
  2. 各组内必须能平分核桃（当然是不能打碎的）
  3. 尽量提供满足 1,2 条件的最小数量（节约闹革命嘛）

输入描述

输入一行 \(a,b,c\)，都是正整数，表示每个组正在加班的人数，用空格分开\((a,b,c<30)\)

输出描述

输出一个正整数，表示每袋核桃的数量。

示例

输入

1
2 4 5

输出

1
20

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
// 辗转相除法求最大公约数
int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
} 

int lcm(int x, int y) {
    return x / gcd(x, y) * y; // 先除后乘，防止溢出
}

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int result = lcm(a, b);
    cout << lcm(result, c) << endl;
}

e.g.52[蓝桥杯 2019 省 B] 等差数列📌

题目描述

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 \(N\) 个整数。

现在给出这 \(N\) 个整数，小明想知道包含这 \(N\) 个整数的最短的等差数列有几项？

输入格式

输入的第一行包含一个整数 \(N\)。

第二行包含 \(N\) 个整数 \(A_1,A_2,\cdots,A_N\)。（注意 \(A_1 ∼ A_N\) 并不一定是按等差数列中的顺序给出 )。

输出格式

输出一个整数表示答案。

样例

样例输入 

1
2
5
2 6 4 10 20

样例输出 

1
10

提示

包含 2,6,4,10,20 的最短的等差数列是 2,4,6,8,10,12,14,16,18,20。

对于所有评测用例，\(2 \le N \le 10^5\)，\(0 \le A_i \le 10^9\)。

蓝桥杯 2019 年省赛 B 组 H 题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int a[1000005];
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    int d = 0;
    for (int i = 1; i <= n-1; i++) {
        d = __gcd(d, a[i + 1] - a[i]);
    }
    if (d == 0)
        cout << n << endl;
    else
        cout << (a[n] - a[1]) / d + 1 << endl;
}