首页 › 题库 › GESP编程能力等级认证 › 1 初等数论

GESP-C++五级 题库

共 130 道题 ,第 6 / 7 页 · 按题型筛选,点「查看答案」核对解析
章节 1 初等数论 清除
101 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

小杨在生日聚会时拿一块H*W的巧克力招待来的K个小朋友,保证每位小朋友至少能获得一块相同大小的巧克力。那么小杨想分出来最大边长的巧克力可以使用二分法。(   )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
102 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

小杨设计了一个拆数程序,它能够将任意的非质数自然数N转换成若干个质数的乘积,这个程序是可以设计出来的。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
103 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

下面的C++代码能实现十进制正整数N转换为八进制并输出。(   )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
104 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

小杨想写一个程序来算出正整数N有多少个因数,经过思考他写出了一个重复没有超过N/2次的循环就能够算出来了。(   )(2023年12月C++五级)

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
105 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

TCP/IP的传输层的两个不同的协议分别是UDP和TCP。(2023.9C++五级)

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
106 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

在特殊情况下流程图中可以出现三角框和圆形框。(2023.9C++五级)

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
107 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

找出自然数 N 以内的所有质数,常用算法有埃氏筛法和线性筛法,其中埃氏筛法效率更高。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
108 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

C++语言中的 qsort 库函数是不稳定排序。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
109 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

质数的判定和筛法的目的并不相同,质数判定旨在判断特定的正整数是否为质数,而质数筛法意在筛选出范围内的所有质数。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
110 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

下面的C++代码执行后将输出 0 5 1 6 2 3 4 。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
111 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

数字移动

时间限制:1.0 s

内存限制:512.0 MB

题目描述

输入格式

输出格式

输出一行,代表满足要求的 的最小值。

输入样例

6
1 2 1 3 2 3

输出样例

2

数据范围

答案与解析
参考答案
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int b[N];
int pos;

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

    int left = 1, right = 1e6, ans = 1e6;
    while (left <= right) {
        int mid = (left + right) / 2;
        bool possible = true;
        pos = 0;

        for (int i = 0; i < n; i++) {
            if (a[i] > mid) {
                b[pos++] = a[i];
            }
        }

        for (int i = 0; i < pos; i += 2) {
            if (b[i] != b[i + 1]) {
                possible = false;
                break;
            }
        }

        if (possible) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}
题目详情
112 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

相等序列

时间限制: 1.0 s

内存限制:512.0 MB

题目描述

小 A 有一个包含 N 个正整数的序列A = {A1 , A2 , · ·  ,AN} 。小 A 每次可以花费 1 个金币执行以下任意一种操作:

 选择序列中一个正整数 Ai ( 1 ≤ i ≤ N) ,将 Ai 变为 Ai * P ,P 为任意质数;

 选择序列中一个正整数 Ai ( 1 ≤ i ≤ N) ,将 Ai 变为 Ai /P ,P 为任意质数,要求Ai能被p整除。

小 A 想请你帮他计算出令序列中所有整数都相同 ,最少需要花费多少金币。

输入格式

第一行一个正整数N ,含义如题面所⽰ 。

第二行包含 N 个正整数 A1 , A2 , ·  … ,AN ,代表序列 A。

输出格式

输出一行 ,代表最少需要花费的金币数量。

输入样例

5
10  6  35  105  42

输出样例

8

数据范围

对于60%的测试点 ,保证 1 ≤ N, Ai ≤ 100 。

对于所有测试点 ,保证 1 ≤ N, Ai ≤ 105 。

答案与解析
参考答案
#include <iostream>
using namespace std;
const int N = 100010;
int num[N][20];
int n, a[N];

void calc_prime_factor(int x)
{
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            int cnt = 0;
            while (x % i == 0)
            {
                x /= i;
                cnt++;
            }
            num[i][cnt]++;
        }
    }
    if (x > 1)
    {
        num[x][1]++;
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        calc_prime_factor(a[i]);
    }

    long long ans = 0;
    for (int i = 2; i < 100001; i++)
    {
        int pos = 0;
        for (int j = 0; j < 20; j++)
        {
            pos += num[i][j];
        }
        num[i][0] = n - pos;

        int median_exponent = 0;
        pos = 0;
        for (int j = 0; j < 20; j++)
        {
            pos += num[i][j];
            if (pos * 2 >= n)
            {
                median_exponent = j;
                break;
            }
        }

        for (int j = 0; j < 20; j++)
        {
            ans += num[i][j] * abs(j - median_exponent);
        }
    }
    printf("%lld\n", ans);
    return 0;
}
题目详情
113 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

数字选取

答案与解析
参考答案
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
int n, p[N], cnt, minp[N];
bool np[N], used[N];

int main() {
    scanf("%d", &n);
    // 欧拉筛,同时求最小质因子minp
    for (int i = 2; i <= n; i++) {
        if (!np[i]) {
            p[++cnt] = i;
            minp[i] = i;
        }
        for (int j = 1; j <= cnt && 1LL * i * p[j] <= n; j++) {
            np[i * p[j]] = true;
            minp[i * p[j]] = p[j];
            if (i % p[j] == 0) break;
        }
    }
    int k = n / 2;
    int res = 0;
    for (int i = k + 1; i <= n; i++) {
        int prime = minp[i];
        if (!used[prime]) {
            used[prime] = true;
            res++;
        }
    }
    res += 1; // 选数字1
    printf("%d\n", res);
    return 0;
}
题目详情
114 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

有趣的数字和

答案与解析
参考答案
#include <algorithm>
#include <cstdio>
#include <utility>
using namespace std;

int L, R;
long long ans;

pair<int, long long> cal2(int n, int p) {
    if (n == 0) {
        return {1 - p, 0};
    }
    if (n == 1) {
        return {1, p};
    }
    return {(n + 1) / 2, 1LL * n * (n + 1) / 4};
}

pair<int, long long> cal(int n, int p) {
    if (n <= 1) {
        return cal2(n, p);
    }
    long long x = 1LL << (31 - __builtin_clz(n)); // ≤n的最大2的幂
    auto left_part = cal2(x - 1, p);
    auto right_part = cal(n - x, 1 - p);
    return {
        left_part.first + right_part.first,
        left_part.second + right_part.second + x * right_part.first
    };
}

int main() {
    scanf("%d%d", &L, &R);
    ans += cal(R, 1).second;
    ans -= cal(L - 1, 1).second;
    printf("%lld\n", ans);
    return 0;
}
题目详情
115 简答题 偏难 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;
}
题目详情
116 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 1.2 最大公约数与最小公倍数

最大公因数

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

【问题描述】

对于两个正整数 a、b,它们的最大公因数记为 gcd(a, b)。对于 k >=3 个正整数 c1、c2、……、ck,它们的最大公因数为:

gcd(c1, c2, ……, ck) = gcd(gcd(c1, c2, ……, c(k-1), ck)

给定 n 个正整数 a1、a2、……、an 以及 q 组询问。对于第 i(1<=i<=q)组询问,请求出 a1+i、a2+i、……、an+i 的最大公因数,也即 gcd(a1+i, a2+i, …… , an+i)。

【输入描述】

第一行,两个正整数 n、q,分别表示给定正整数的数量,以及询问组数。

第二行, n 个正整数 a1、a2、……、an。

【输出描述】

输出共 q 行,第 i 行包含一个正整数,表示 a1+i、a2+i、……、an+i  的最大公因数。

【样例输入1】

5 3
6 9 12 18 30

【样例输出1】

1
1
3

【样例输入2】

3 5
31 47 59

【样例输出2】

4
1
2
1
4

【数据范围】

对于60%的测试点,保证 1 <= n <= 1000,1 <= q <= 10。

对于所有测试点,保证 1 <= n、q <= 10^5,1 <= ai <= 1000。

答案与解析
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n, q, a[N], g;
int gcd(int a, int b) {
    if (a == 0 || b == 0)
        return a + b;
    return gcd(b, a % b);
}
int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 2; i <= n; i++)
        g = gcd(g, a[i] - a[i - 1]);
    for (int i = 1; i <= q; i++)
        cout << gcd(g, a[1] + i) << endl;
    return 0;
}
题目详情
117 简答题 偏难 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;
}
题目详情
118 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

原根判断

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

【问题描述】

小 A 知道,对于质数 p 而言,p 的原根 g 是满足以下条件的正整数:

其中 a mod p 表示 a 除以 p 的余数。

小 A 现在有一个整数 T,请你帮他判断 a 是不是 p 的原根。

【输入描述】

第一行,一个正整数 T,表示测试数据组数。

每组测试数据包含一行,两个正整数 a、p。

【输出描述】

对于每组测试数据,输出一行,如果 a 是 p 的原根则输出 Yes ,否则输出 No 。

【样例输入1】

3
3 998244353
5 998244353
7 998244353

【样例输出1】

Yes
Yes
No

【数据范围】

对于 40% 的测试点,保证 3<=p<=1000。

对于所有测试点,保证 1<=T<=20, 3<=p<=10^9,1<a<p , p为质数。

对于所有测试点,保证 ,-100<= A(i,j) <=100 。

答案与解析
参考答案
#include <cstdio>
using namespace std;
int a, p;
int ans;
int fpw(int b, int e) {
    if (e == 0)
        return 1;
    int r = fpw(b, e >> 1);
    r = 1ll * r * r % p;
    if (e & 1)
        r = 1ll * r * b % p;
    return r;
}
void check(int e) {
    if (fpw(a, e) == 1)
        ans = 0;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &a, &p);
        ans = 1;
        int phi = p - 1, r = phi;
        for (int i = 2; i * i <= phi; i++)
            if (phi % i == 0) {
                check(phi / i);
                while (r % i == 0)
                    r /= i;
            }
        if (r > 1)
            check(phi / r);
        printf(ans ? "Yes\n" : "No\n");
    }
    return 0;
}
题目详情
119 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

奇妙数字

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨认为一个数字 x 是奇妙数字当且仅当 x=pa,其中 p 为任意质数且 a 为正整数。例如, 8=23,所以 8 是奇妙数字,而 6 不是。

对于一个正整数 n ,小杨想要构建一个包含 m 个奇妙数字的集合{x1,x2,...,xm},使其满足以下条件:

集合中不包含相同的数字。

x1∗x2∗...∗xm是 n  的因子(即x1,x2,...,xm这 m 个数字的乘积是 n 的因子)。

小杨希望集合包含的奇妙数字尽可能多,请你帮他计算出满足条件的集合最多包含多少个奇妙数字。

输入格式

第一行包含一个正整数 n ,含义如题面所示。

输出格式

输出一个正整数,代表满足条件的集合最多包含的奇妙数字个数。


输入样例

128

输出样例

3

样例解释

关于本样例,符合题意的一个包含 3 个奇妙数字的集合是 2,4,8。首先,因为2=21,4=22,8=23, 所以 2,4,8 均为奇妙数字。同时,2∗4∗8=64 是 128 的因子。

由于无法找到符合题意且同时包含 4 个奇妙数字的集合,因此本样例的答案为 3  。

对于全部数据,保证有 2≤n≤1012。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
ll calc(ll x){
	int ans = 0;
	ll tmp=1;
	while(x>=tmp){
		ans++;
		x-=tmp;
		tmp++;
	}
	return ans;
}
int main(){
	ll n;
	cin>>n;
	ll ans = 0;
	for(ll i=2;i*i<=n;i++){
		if(n%i==0){
			int cnt = 0;
			while(n%i==0){
				cnt++;
				n/=i;
			}
			ans+=calc(cnt);
		}
	}
	if(n!=1){
		ans+=calc(1);
	}
	cout<<ans<<"\n";
}
题目详情
120 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

武器强化

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有 n 种武器和 m 种强化材料。第 i 种强化材料会适配第 pi 种武器,小杨可以花费 ci 金币将该材料对应的适配武器修改为任意武器。

小杨最喜欢第 1 种武器,因此他希望适配该武器的强化材料种类数严格大于其他的武器,请你帮小杨计算为了满足该条件最少需要花费多少金币。

输入格式

第一行包含两个正整数 n,m,含义如题面所示。

之后 m 行,每行包含两个正整数 pi,ci,代表第 i 种强化材料的适配武器和修改花费。

输出格式

输出一个整数,代表能够使适配第 1 种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。


输入样例

4 4

1 1

2 1

3 1

3 2

输出样例

1

样例解释

花费 1,将第三种强化材料的适配武器由 3 改为 1。此时,武器 1 有 2 种强化材料适配,武器 2 和武器 3 都各有 1 种强化材料适配。满足适配第 1 种武器的强化材料种类数严格大于其他的武器。

对于全部数据,保证有 1≤n,m≤1000,1≤pi≤n,1≤ci≤109。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, m;
int cnt[1010];
vector<int> cs[1010];

ll calc(int aim) {
	int cur_cnt = cnt[1];
	ll res = 0;
	vector<int> tmp;
	for (int i = 2; i<=n; i++) {
		int buy = max((int)cs[i].size() - aim + 1, 0);
		for (int j = 0; j < buy; ++j) {
			res += (ll)cs[i][j];
		}
		cur_cnt += buy;
		for (int j = buy; j < cs[i].size(); ++j) {
			tmp.push_back(cs[i][j]);
		}
	}
	sort(tmp.begin(), tmp.end());
	for (int i = 0; i < aim - cur_cnt; i++) {
		res += (ll)tmp[i];
	}
	return res;
}

signed main() {
	// freopen("06.in", "r", stdin);
	cin >> n >> m;
	for (int i = 1; i <=m; i++) {
		int p, c;
		cin >> p >> c;
		cnt[p]++;
		cs[p].push_back(c);
	}
	for (int i = 1; i <=n; i++) {
		sort(cs[i].begin(), cs[i].end());
	}
	ll ans = 1e18;
	for (int i = max(cnt[1], 1); i <= m; ++i) {
		ans = min(ans, calc(i));
	}
	cout << ans << "\n";
}
题目详情