GESP 2026年C++五级编程题解析

202603-1 有限不循环小数#

题目描述

若 $\frac{1}{a}$ 可化为一个有限的，不循环的小数，则称 $a$ 为终止数。

请你求出在 $L$ 到 $R$ 中终止数的数量。

输入格式

输入一行，包含两个整数 $L,R$ 。

输出格式

输出一行，包含一个整数，表示 $L$ 到 $R$ 中终止数的数量。

样例输入 1

2 11

样例输出 1

提示

【样例解释】

在 $[2,11]$ 终止数有 $2$ 、 $4$ 、 $5$ 、 $8$ 、 $10$ 。

【数据范围】

保证 $1 \le L \le R \le 10^6$ 。

代码解析

这道题代码很简单，考察的重点是数论，一个数字如果是终止数，那么它的质因子只能有 $2$ 和 $5$ ，通过题目给出的 2、4、5、8、10 花点时间思考也可以找到这个规律，所有我们只需要判断每个数字是否只包含 $2$ 和 $5$ 这两个质因子即可。

1
#include <bits/stdc++.h>
2
using namespace std;
3
bool check(int a) {
4
    while (a % 2 == 0) a /= 2;
5
    while (a % 5 == 0) a /= 5;
6
    if (a == 1) return true;
7
    return false;
8
}
9
int main() {
10

11
    int l, r, cnt = 0;
12
    cin >> l >> r;
13
    for (int i = l; i <= r; i++)
14
        if (check(i))
15
            cnt++;
16
    cout << cnt;
17

18
    return 0;
19
}

202603-2 找数#

题目描述

给定一个包含 $n$ 个互不相同的正整数的数组 $A$ 与一个包含 $m$ 个互不相同的正整数的数组 $B$ ，请你帮忙计算有多少个数在数组 $A$ 与数组 $B$ 中均出现。

输入格式

第一行包含两个整数 $n,m$ 。

第二行包含 $n$ 个正整数 $a_1,a_2,\cdots,a_n$ 表示数组 $A$ 。

第三行包含 $m$ 个正整数 $b_1,b_2,\cdots,b_m$ 表示数组 $B$ 。

输出格式

输出一个整数，表示在数组 $A$ 与数组 $B$ 中均出现的数的个数。

样例输入 1

3 5
4 2 3
3 1 5 4 6

样例输出 1

提示

【样例解释】

样例 1 中， $4$ 、 $3$ 在数组 $A$ 与 $B$ 中均出现。

【数据范围】

对于 $40\%$ 的数据，保证 $1 \leq n,m \leq 1000$ 。

对于 $100\%$ 的数据，保证 $1 \leq n,m \leq 10^5$ ， $1 \leq a_i,b_i \leq 10^9$ 。

代码解析

这道题代码也很简单，我们先将数组 $A$ 排序，然后对于数组 $B$ 中的每个数 $b$ ，我们使用二分查找在数组 $A$ 中查找是否存在 $b$ ，如果存在，那么 $b$ 就是在数组 $A$ 与数组 $B$ 中均出现的数。

1
#include <bits/stdc++.h>
2
using namespace std;
3
int n, m, a[100005], cnt = 0;
4
// 二分查找
5
int search (int l, int r, int x) {
6
    while (l != r) {
7
        int mid = (l + r) / 2;
8
        if (a[mid] >= x) r = mid;
9
        else l = mid+1;
10
    }
11
    return l;
12
}
13

14
int main() {
15

16
    cin >> n >> m;
17
    for (int i = 0; i < n; i++)
18
        cin >> a[i];
19
    sort(a, a+n);
20
    int b;
21
    for (int j = 0; j < m; j++){
22
        cin >> b;
23
        if (a[search(0, n, b)] == b)
24
            cnt++;
25
    }
26
    cout << cnt;
27

28
    return 0;
29
}

或者直接使用 STL 中的 lower_bound 函数来实现二分查找，代码如下：

1
#include <bits/stdc++.h>
2
using namespace std;
3
int main() {
4

5
    int n, m, a[100005], cnt = 0;
6
    cin >> n >> m;
7
    for (int i = 0; i < n; i++)
8
        cin >> a[i];
9
    sort(a, a+n);
10
    int b;
11
    for (int j = 0; j < m; j++){
12
        cin >> b;
13
        if (a[lower_bound(a, a+n, b)-a] == b)
14
            cnt++;
15
    }
16
    cout << cnt;
17

18
    return 0;
19
}

202606-1 排排坐#

题目描述

老师正在和小朋友们分糖果。

小朋友们先在自己的手上写一个数字，然后坐成一排。

老师分发糖果的规则是：每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。

现在小朋友们都已经在自己手上写上了数字。

请帮小朋友们安排合适的座位顺序，使得小朋友们分到的糖果总量最大，输出这个最大值。

输入格式

输入 $2$ 行，

第一行为一个正整数 $n$ ，表示小朋友的个数；

第二行为 $n$ 个正整数 $a_1, a_2, \cdots, a_n$ ，表示小朋友们手上的数字，整数之间以空格分隔。

输出格式

输出一个整数，表示小朋友们可能分到的最大糖果总数量。

样例输入 1

5
7 5 8 9 3

样例输出 1

提示

【样例解释】

小朋友安排座位后从左向右每人手上数字依次是： $9, 8, 7, 5, 3$ 。

这时可以得到最多的糖果： $(9) + (9 + 8) + (9 + 8 + 7) + (9 + 8 + 7 + 5) + (9 + 8 + 7 + 5 + 3) = 111$ 。

【数据范围】

$1 \le n \le 1000$ ， $1 \le a_i \le 1000$ 。

代码解析

贪心算法，每个孩子的糖果为他左边的所有孩子手上的的数字和，要想让每个孩子获得的糖果数量最多，我们需要将越大的数字排在越前面的位置，只需要从大到小排序，再计算即可。

1
#include <bits/stdc++.h>
2
using namespace std;
3
int main() {
4

5
    int a[1005], n;
6
    cin >> n;
7
    for (int i = 0; i < n; i++)
8
        cin >> a[i];
9
    sort(a, a+n, greater<int>());
10

11
    int sum = 0, ans = 0;
12
    for (int i = 0; i < n; i++) {
13
        ans += a[i];
14
        sum += ans;
15
    }
16
    cout << sum;
17

18
    return 0;
19
}

202606-2 晚宴#

题目描述

小明去参加晚宴。晚宴中有 $n$ 个菜肴，每个菜肴都有一个美味度，第 $i$ 个菜肴的美味度为 $v_i$ 。

晚宴规定小明只能恰好选取两道菜肴，并且这两道菜肴的美味度必须要互质（即最大公约数为 $1$ ）。

请帮助小明选取两道菜肴，使得两道菜肴美味度之和最大。

输入格式

输入 $2$ 行，

第一行为一个正整数 $n$ ，表示菜肴的个数；

第二行为 $n$ 个整数 $v_1, v_2, \cdots, v_n$ 表示菜肴的美味度，整数之间以空格分隔。

输出格式

输出一个整数，表示两道互质菜肴美味度之和的最大值。

样例输入 1

5
3 5 7 35 105

样例输出 1

提示

【样例解释 1】

最优选择是 $3$ 和 $35$ 。

注意到， $105$ 与其他任意菜肴的最大公约数都大于 $1$ ，因此无法参与合法选择。

【数据范围】

$2 \le n \le 1000$ , $1 \le v_i \le 1000000$ 。

数据保证不存在相同美味度的菜肴。

数据保证至少存在一种选取两道菜肴的方案。

代码解析

互质数的判断使用辗转相除法，数据范围只有 $1000$ ，直接暴力枚举即可。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
bool isp(int a, int b) {
5
    while (a % b) {
6
        int t = a % b;
7
        a = b;
8
        b = t;
9
    }
10
    return b == 1;
11
}
12

13
int main() {
14

15
    int n, ans = 0, a[1005];
16
    cin >> n;
17
    for (int i = 0; i < n; i++)
18
        cin >> a[i];
19

20
    for (int i = 0; i < n; i++)
21
        for (int j = i+1; j < n; j++)
22
            if (isp(a[i], a[j]))
23
                ans = max (ans , a[i]+a[j]);
24

25
    cout << ans;
26

27
    return 0;
28
}