首页 › 题库 › GESP编程能力等级认证 › 1.3 同余与模运算

GESP-C++五级 题库

共 9 道题 · 按题型筛选,点「查看答案」核对解析
章节 1.3 同余与模运算 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

假设我们有两个数 a=38和b=14,它们对模 同余,即 a=b(mod m)。以下哪个值不可能是 m?

A
3
B
4
C
6
D
9
答案与解析
正确答案:D
根据同余定义,若 a ≡ b (mod m),则 m 必须整除 |a - b|。计算 |a - b| 的值,得到一个正整数差。所有可能的 m 值必须是该差值的正因数。列出该差值的所有正因数,构成可能模数的集合。任何不属于该集合的正整数,均不可能作为满足同余关系的模。通过判断各候选值是否为该差值的因数,可确定其是否可能为 m。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

有如下函数 fun ,则 fun(20, 12) 的返回值为( )。

int fun(int a, int b) {
	if (a % b == 0)
		return b;
	else
		return fun(b, a % b);
}


A
20
B
12
C
4
D
2
答案与解析
正确答案:C

函数为辗转相除求两数的最大公约数,结果为4,如果没有看出函数作用,也可以手动模拟递归过程。

题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

现在有 n 个人要过河,每只船最多载2人,船的承重为100kg。下列代码中,数组 weight 中保存有 n 个人的体重(单位为kg),已经按从小到大排好序,代码输出过河所需要的船的数目,采用的思想为( )。

int i, j;
int count = 0;
for (i = 0, j = n - 1; i < j; j--) {
	if (weight[i] + weight[j] <= 100) {
		i++;
	}
	count++;
}
printf("过河的船数:%d\n", count);


A
枚举算法
B
贪心算法
C
迭代算法
D
递归算法
答案与解析
正确答案:B

重量已经按照从小到大排序了,然后双指针处理,双指针的过程为最轻的人和最重的人尝试能否在同一个船上,如果可以,那么他们在同一个船上,否则,当前最重的人不能和其他人在一个船上,得单独一条船。采用的是贪心的思想。

题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

下面C++代码用于将输入金额换成最少币种组合方案,其实现算法是( )。

#include <iostream>
using namespace std;

#define N_COINS 7
int coins[N_COINS] = {100, 50, 20, 10, 5, 2, 1}; //货币面值,单位相同
int coins_used[N_COINS];

void find_coins(int money) {
	for (int i = 0; i < N_COINS; i++) {
		coins_used[i] = money / coins[i];
		money = money % coins[i];
	}
	return;
}
int main() {
	int money;
	cin >> money; //输入要换算的金额
	
	find_coins(money);
	for (int i = 0; i < N_COINS; i++)
		cout << coins_used[i] << endl;
		
	return 0;
}
A
枚举算法
B
贪心算法
C
迭代算法
D
递归算法
答案与解析
正确答案:B

贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优(最有利)的选择,以期望最终能够达到全局最优解。在这段代码中,每次循环都选择当前面值最大的硬币进行尽可能多的使用,从而达到最少硬币数量的组合方案。

算法实现分析:

数组coins 存储了面值从大到小的硬币面额{100, 50, 20, 10, 5, 2, 1}。

函数find_coins() 中使用了一个循环遍历所有硬币面额。在每次循环中,计算当前金额money 可以使用的当前面额硬币数量,并更新剩余金额money。

循环结束后,coins_used 数组存储了每种面额硬币的使用数量,以达到组合最少硬币数量的目的。

选择最优:由于每次都选择当前最大面额的硬币,贪心算法能够在保证每次选择最优的情况下,快速得到全局最优解,即使用最少数量的硬币来组合金额。

根据代码实现方式和贪心算法的特性,这段C++代码确实属于贪心算法。

题目详情
5 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

下面的C++代码用于输出每个数对应的质因数列表,输出形如: {5: [5], 6: [2, 3], 7: [7], 8: [2, 2, 2]} 。( )

int main() {
    int n, m;
    cin >> n >> m;
    if (n > m) swap(n, m);
    map<int, vector<int>> prime_factor;
    for (int i = n; i <= m; ++i) {
        int j = 2, k = i;
        while (k != 1) {
            if (k % j == 0) {
                prime_factor[i] = prime_factor[i] + j;
                k /= j;
            } else {
                ++j;
            }
        }
    }
    for (auto& p : prime_factor) {
        cout << p.first << ": ";
        for (int v : p.second)
            cout << v << " ";
        cout << endl;
    }
    return 0;
}
A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
6 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

奖品兑换

时间限制:1 s,内存限制:512 MB

【问题描述】

班主任给上课专心听讲、认真完成作业的同学们分别发放了若干张课堂优秀券和作业优秀券。同学们可以使用这两种券找班主任兑换奖品。

具体来说,可以使用 a 张课堂优秀券和 b 张作业优秀券兑换一份奖品,或者使用 b 张课堂优秀券和 a 张作业优秀券兑换一份奖品。

现在小 A 有 n 张课堂优秀券和 m 张作业优秀券,他最多能兑换多少份奖品呢?

【输入描述】

第一行,两个正整数 n、m,分别表示小 A 持有的课堂优秀券和作业优秀券的数量。

第二行,两个正整数 a、b,表示兑换一份奖品所需的两种券的数量。

【输出描述】

输出共一行,一个整数,表示最多能兑换的奖品份数。

【样例输入1】

8 8
2 1

【样例输出1】

5

【样例输入2】

314159 2653589
27 1828

【样例输出2】

1599

【数据范围】

对于60%测试点,保证 1 <= a、b <= 100,1 <= n、m <= 500。

对于所有测试点,保证 1 <= a、b <= 10^4,1 <= n、m <= 10^9。

答案与解析
参考答案
#include <iostream>
using namespace std;
int n, m, a, b;
int l, r;
int check(int v) {
    long long x, y, t;
    x = 1ll * v * a;
    y = 1ll * v * b;
    if (y > m) {
        t = (y - m + (b - a) - 1) / (b - a);
        y -= t * (b - a);
        x += t * (b - a);
    }
    return x <= n && y <= m;
}
int main() {
    cin >> n >> m >> a >> b;
    if (n > m)
        swap(n, m);
    if (a > b)
        swap(a, b);
    if (a == b) {
        cout << n / a << endl;
        return 0;
    }
    l = 0;
    r = n;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    cout << r << endl;
    return 0;
}
题目详情
7 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

平均分配

时间限制:1 s,内存限制:512 MB

【问题描述】

小 A 有 2n 件物品,小 B 和小 C 想从小 A 手上买走这些物品。对于第 i 件物品,小 B 会以 bi 的价格购买,而小 C 会以 ci 的价格购买。

为了平均分配这 2n 件物品,小 A 决定小 B 和小 C 各自只能买走恰好 n 件物品。你能帮小 A 求出他卖出这 2n 件物品所能获得的最大收入吗?

【输入描述】

第一行,一个正整数 n。

第二行, 2n 个整数 b1、b2、……、b(2n)。

第三行, 2n 个整数 c1、c2、……、c(2n)。

【输出描述】

一行,一个整数,表示答案。

【样例输入1】

3
1 3 5 6 8 10
2 4 6 7 9 11

【样例输出1】

36

【样例输入2】

2
6 7 9 9
1 2 10 12

【样例输出2】

35

【数据范围】

对于 20% 的测试点,保证 1<=n<=8。

对于另外 20% 的测试点,保证 0<=bi<=1,0<=ci<=1 。

对于所有测试点,保证 0<=n<=10^5,0<=bi<=10^9 ,0<=ci<=10^9 。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
long long b[N], c[N], d[N];
long long ans;
int main() {
    scanf("%d", &n);
    assert(1 <= n && n <= 1e5);
    for (int i = 1; i <= 2 * n; i++)
        scanf("%lld", &b[i]), assert(0 <= b[i] && b[i] <= 1e9);
    for (int i = 1; i <= 2 * n; i++)
        scanf("%lld", &c[i]), assert(0 <= c[i] && c[i] <= 1e9);
    for (int i = 1; i <= 2 * n; i++) {
        ans += b[i];
        d[i] = c[i] - b[i];
    }
    sort(d + 1, d + 2 * n + 1);
    for (int i = n + 1; i <= 2 * n; i++)
        ans += d[i];
    printf("%lld\n", ans);
    return 0;
}
题目详情
8 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

小杨的幸运数

时间限制:1.0 s

内存限制:128.0 MB

问题描述

小杨认为,所有大于等于 的完全平方数都是他的超级幸运数。

小杨还认为,所有超级幸运数的倍数都是他的幸运数。自然地,小杨的所有超级幸运数也都是幸运数。

对于一个非幸运数,小杨规定,可以将它一直+1,直到它变成一个幸运数。我们把这个过程叫做幸运化。例如,如果a=4,那么4是最小的幸运数,而1不是,但我们可以连续对1做3次+1操作,使其变为4,所以我们可以说,1幸运化后的结果是4。

现在,小杨给出N个数,请你首先判断它们是不是幸运数;接着,对于非幸运数,请你将它们幸运化。

输入描述

第一行 2 个正整数a,N。

接下来N行,每行一个正整数x,表示需要判断(幸运化)的数。

输出描述

输出N行,对于每个给定的x,如果它是幸运数,请输出 lucky ,否则请输出将其幸运化后的结果。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

2 4
1
4
5
9

样例输出 1

4
lucky
8
lucky

样例解释 1

1虽然是完全平方数,但它小于a,因此它并不是超级幸运数,也不是幸运数。将其进行3次+1操作后,最终得到幸运数 。

4是幸运数,因此直接输出 lucky 。

5不是幸运数,将其进行3次+1操作后,最终得到幸运数8。

9是幸运数,因此直接输出 lucky 。


样例输入 2

16 11
1
2
4
8
16
32
64
128
256
512
1024

样例输出 2

16
16
16
16
lucky
lucky
lucky
lucky
lucky
lucky
lucky

数据规模

对于30%的测试点,保证a,x≤100,N≤100。

对于60%的测试点,保证a,x≤106。

对于所有测试点,保证a≤1000001;保证N≤2×105;保证1≤x≤1000001。

答案与解析
参考答案
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <string>

using namespace std;
const int N = 1001 * 1001;
const double eps = 1e-8;
bool is_lucky[N + 5];
int next_lucky[N + 5];
void init() {}
int main() {
  int a, T;
  scanf("%d%d", &a, &T);
  for (int i = 1; i <= N; i++) {
    int t = int(sqrt(i) + eps);
    if (i >= a && t * t == i)
      is_lucky[i] = 1;
    if (!is_lucky[i])
      continue;
    for (int j = i + i; j <= N; j += i)
      is_lucky[j] = 1;
  }
  for (int i = N; i; i--)
    next_lucky[i] = is_lucky[i] ? i : next_lucky[i + 1];
  while (T--) {
    int x;
    scanf("%d", &x);
    if (is_lucky[x])
      cout << "lucky" << endl;
    else
      cout << next_lucky[x] << endl;
  }
  return 0;
}
题目详情
9 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

烹饪问题

时间限制:1.0 s

内存限制:128.0 MB

问题描述

有N种食材,编号从0至N-1,其中第 种食材的美味度为 。

不同食材之间的组合可能产生奇妙的化学反应。具体来说,如果两种食材的美味度分别为x和y,那么它们的契合度为x and y。

其中,and运算为按位与运算,需要先将两个运算数转换为二进制,然后在高位补足0,再逐位进行与运算。例如,12与6的二进制表示分别为 1100 和 0110 ,将它们逐位进行与运算,得到 0100 ,转换为十进制得到4,因此。在 C++ 或 Python 中,可以直接使用 & 运算符表示与运算。

现在,请你找到契合度最高的两种食材,并输出它们的契合度。

输入描述

第一行一个整数N,表示食材的种数。

接下来一行N个用空格隔开的整数,依次为a0,…,aN-1,表示各种食材的美味度。

输出描述

输出一行一个整数,表示最高的契合度。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

3
1 2 3

样例输出 1

2

样例解释 1

可以编号为1,2的食材之间的契合度为2 and 3=2,是所有食材两两之间最高的契合度。


样例输入 2

5
5 6 2 10 13

样例输出 2

8

样例解释 1

可以编号为3,4的食材之间的契合度为10 and 13=8,是所有食材两两之间最高的契合度。


数据规模

对于40%的测试点,保证N≤1000;

对于所有测试点,保证N≤106,0≤ai≤2147483647。

答案与解析
参考答案
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;
const int MAX_N = int(1e6) + 100;
int a[MAX_N];
int sort(int l, int r, int k) {
  while (l <= r) {
    while ((l <= r) && (a[l] >> k & 1))
      l++;
    while ((l <= r) && (!(a[r] >> k & 1)))
      r--;
    if (l <= r)
      swap(a[l++], a[r--]);
  }
  return r;
}
int main() {
  int n, j, ans = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    scanf("%d", &a[i]);
  for (int i = 31; i >= 0; i--)
    if ((j = sort(1, n, i)) >= 2) {
      ans = ans | 1 << i;
      n = j;
    }
  printf("%d\n", ans);
  return 0;
}
题目详情