首页 › 题库 › GESP编程能力等级认证 › GESP-C++五级

GESP-C++五级 题库

共 297 道题 ,第 15 / 15 页 · 按题型筛选,点「查看答案」核对解析
281 简答题 偏难 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;
}
题目详情
282 简答题 偏难 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;
}
题目详情
283 简答题 偏难 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;
}
题目详情
284 简答题 偏难 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";
}
题目详情
285 简答题 偏难 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";
}
题目详情
286 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

小杨的武器

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有 n 种不同的武器,他对第 i ii 种武器的初始熟练度为ci。

小杨会依次参加 m 场战斗,每场战斗小杨只能且必须选择一种武器使用,假设小杨使用了第 i 种武器参加了第 j 场战斗,战斗前该武器的熟练度为ci′,则战斗后小杨对该武器的熟练度会变为 ci′+aj。需要注意的是,aj可能是正数,0 或负数,这意味着小杨参加战斗后对武器的熟练度可能会提高,也可能会不变,还有可能降低。

小杨想请你编写程序帮他计算出如何选择武器才能使得 m 场战斗后,自己对 n 种武器的熟练度的最大值尽可能大。

输入格式

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

第二行包含 n 个正整数 c1,c2,...,cn,代表小杨对武器的初始熟练度。

第三行包含 m 个正整数 a1,a2,...,am,代表每场战斗后武器熟练度的变化值。

输出格式

输出一个整数,代表 m 场战斗后小杨对 n 种武器的熟练度的最大值最大是多少。


输入样例

2 2
9 9
1 -1

输出样例

10

一种最优的选择方案为,第一场战斗小杨选择第一种武器,第二场战斗小杨选择第二种武器。

对于全部数据,保证有 1≤n,m≤105,−104≤ci,ai≤104。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int a[N], c[N];

int main(){
	int n, m;
	cin>>n>>m;
	int mx = -10000;
	for (int i = 1; i <= n; ++ i){
		cin>>c[i];
		mx = max(mx,c[i]);
	}
	for (int i = 1; i <= m; ++ i){
		cin>>a[i];
	}
	for (int i = 1; i <= m; ++ i){
		if (n == 1 || a[i] > 0){
			mx += a[i];
		}
	}
	cout<<mx<<"\n";
	return 0;
}
题目详情
287 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

挑战怪物

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨正在和一个怪物战斗,怪物的血量为 h ,只有当怪物的血量恰好为 0 时小杨才能够成功击败怪物。

小杨有两种攻击怪物的方式:

物理攻击。假设当前为小杨第 i 次使用物理攻击,则会对怪物造成 2i−1点伤害。

魔法攻击。小杨选择任意一个质数 x (x 不能超过怪物当前血量),对怪物造成 x 点伤害。由于小杨并不擅长魔法,他只能使用至多一次魔法攻击。

小杨想知道自己能否击败怪物,如果能,小杨想知道自己最少需要多少次攻击。

输入格式

第一行包含一个正整数 t ,代表测试用例组数。

接下来是 t 组测试用例。对于每组测试用例,第一行包含一个正整数 h ,代表怪物血量。

输出格式

对于每组测试用例,如果小杨能够击败怪物,输出一个整数,代表小杨需要的最少攻击次数,如果不能击败怪物,输出−1。


输入样例

3
6
188
9999

输出样例

2
4
-1

对于第一组测试用例,一种可能的最优方案为,小杨先对怪物使用魔法攻击,选择质数 5 造成 5 点伤害,之后对怪物使用第 1 次物理攻击,造成21−1=1 点伤害,怪物血量恰好为 0 ,小杨成功击败怪物。

对于全部数据,保证有 1≤t≤10,1≤h≤105。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
vector<int> prime;
bool is_prime[100010];
void Eratosthenes(int n) {
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= n; ++i) is_prime[i] = true;
	for (int i = 2; i <= n; ++i) {
		if (is_prime[i]) {
			prime.push_back(i);
			if ((long long)i * i > n) continue;
			for (int j = i * i; j <= n; j += i)
				is_prime[j] = false;
		}
	}
}
int main() {
	Eratosthenes(100000);
	int t;
	cin>>t;
	while(t--){
		int tmp=1;
		int x;
		cin>>x;
		int ans=0;
		while(1){
			if(is_prime[x]){
				ans++;
				break;
			}
			x-=tmp;
			ans++;
			if(x<=0){
				if(x<0)ans=-1;
					break;
			}
			tmp*=2;
		}
		cout<<ans<<"\n";
	}
}
题目详情
288 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

黑白格

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一个n行m列的网格图,其中每个格子要么是白色,要么是黑色。

小杨想知道至少包含k个黑色格子的最小子矩形包含了多少个格子。

输入格式

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

之后n行,每行一个长度为m的01串,代表网格图第i行格子的颜色,如果为0,则对应格子为白色,否则为黑色。

输出格式

输出一个整数,代表至少包含k个黑色格子的最小子矩形包含格子的数量,如果不存在则输出0。


输入样例

4 5 5
00000
01111
00011
00011

输出样例

6

样例解释

对于样例1,假设(i,j) 代表第i 行第j列,至少包含5个黑色格子的最小子矩形的四个顶点为(2,4),(2,5),(4,4),(4,5),共包含6个格子。

数据范围

对于全部数据,保证有1≤n,m≤100,1≤k≤n×m。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int w[N][N];
int sum[N][N];
int n,m;

int main(){
	int k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=1;j<=m;j++){
			w[i][j]=s[j-1]-'0';
			sum[i][j]=sum[i][j-1]+w[i][j];
		}
	}
	int ans = 0;
	for(int i=1;i<=m;i++){
		for(int j=i;j<=m;j++){
			vector<int> num;
			int now = 0;
			for(int l=1;l<=n;l++){
				int tmp = sum[l][j]-sum[l][i-1];
				now+=tmp;
				num.push_back(now);
				if(now>=k){
					if(ans ==0)ans=(j-i+1)*l;
					else ans=min(ans,(j-i+1)*l);
					int L=1,R=l;
					while (L < R){
						int mid = L + R + 1 >> 1;
						if (now-num[mid-1]>=k) L = mid;
						else R = mid - 1;
					}
					if(now-num[L-1]>=k){
						if(ans ==0)ans=(j-i+1)*(l-L);
						else ans=min(ans,(j-i+1)*(l-L));
					}
				}
			}
		}
	}
	cout<<ans<<"\n";
}

1.二维数组存储对应格子颜色的值

2.使用前缀和的技巧来快速计算任意子矩形内的格子数量。这样一来,不需要重复遍历每个可能的子矩形来计算其中的黑色格子数,从而节省时间

3.通过检查每个可能的子矩形,计算其中的黑色格子数量。找到一个最小的子矩形,使得其中至少有 k 个黑色格子。

4.使用二分查找的技巧,在内部循环中快速定位满足条件的子矩形大小

5.最后,我们输出这个最小子矩形的面积。如果不存在满足条件的子矩形,则输出0

题目详情
289 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

小杨的幸运数字

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨认为他的幸运数字应该恰好有两种不同的质因子,例如,12=2×2×3 的质因子有2,3,恰好为两种不同的质因子,因此12是幸运数字,而30=2×3×5 的质因子有2,3,5,不符合要求,不为幸运数字。

小杨现在有n个正整数,他想知道每个正整数是否是他的幸运数字。

输入格式

第一行包含一个正整数n,代表正整数个数。

之后n行,每行一个正整数。

输出格式

输出n行,对于每个正整数,如果是幸运数字,输出1,否则输出0。


输入样例

3
7
12
30

输出样例

0
1
0

样例解释

7的质因子有7,只有一种。

12的质因子有2,3,恰好有两种。 

30的质因子有2,3,5,有三种。

数据范围

对于全部数据,保证有1≤n≤104,每个正整数ai满足2≤ai≤106。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
const int N = 1e5+10;
int calc(int x) {
	int res = 0;
	set<int> s;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			s.insert(i);
			while (x% i == 0){
				x/= i;
			}
		}
	}
	if (x != 1) {
		s.insert(x);
	}
	return (int)s.size();
}
int a[N];
int main(){
	int n;
	cin>>n;
	long long ans = 0;
	int pre = 0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		int x = calc(a[i]);
		if(x==2)cout<<"1\n";
		else cout<<"0\n";
	}
}

1.计算输入数据的质因子的个数。具体实现中,可以从最小的质数开始试除,统计不重复的质因子个数。

2.当质因子个数为2时,返回1表示是幸运数字,否则返回0。

题目详情
290 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

成绩排序

问题描述

有N名同学,每名同学有语文、数学、英语三科成绩。你需要按如下规则对所有同学的成绩从高到低排序:

1. 比较总分,高者靠前;

2. 如果总分相同,则比较语文和数学两科总分,高者靠前;

3. 如果仍相同,则比较语文和数学两科的最高分,高者靠前;

4. 如果仍相同,则二人并列。

你需要输出每位同学的排名,如遇x人并列,则他们排名相同,并留空后面的x-1个名次。例如,有3名同学并列第1,则后一名同学自动成为第4名。

输入描述

第一行一个整数N,表示同学的人数。

接下来N行,每行三个非负整数ci,mi,ei分别表示该名同学的语文、数学、英语成绩。

保证0≤ci,mi,ei≤150。

输出描述

输出N行,按输入同学的顺序,输出他们的排名。

注意:请不要按排名输出同学的序号,而是按同学的顺序输出他们各自的排名

特别提醒

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

何提示信息。


样例输入 1

6
140 140 150
140 149 140
148 141 140
141 148 140
145 145 139
0 0 0

样例输出 1

1
3
4
4
2
6

数据规模

对于30的测试点,保证N≤100,且所有同学的总分各不相同。

对于所有测试点,保证2≤N≤104。

答案与解析
参考答案
#include <iostream>
#include <algorithm>
#include <tuple>
using namespace std;
const int MAX_N = 10005;
tuple<int, int, int, int> students[MAX_N];
int main() {
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	for (int i = 0; i < N; ++i) {
		int c, m, e;
		cin >> c >> m >> e;
		students[i] = make_tuple(c + m + e, c + m, max(c, m), i);
	}
	sort(students, students + N, greater<tuple<int, int, int, int>>());
	int rank[N];
	int curr_rank;
	tuple<int, int, int> last_student = make_tuple(-1, -1, -1);
	for (int i = 0; i < N; ++i) {
		if (make_tuple(get<0>(students[i]), get<1>(students[i]), get<2>(students[i])) != last_student) {
			last_student = make_tuple(get<0>(students[i]), get<1>(students[i]),get<2>(students[i]));
			curr_rank = i + 1;
		}
		rank[get<3>(students[i])] = curr_rank;
	}
	for (int i = 0; i < N; ++i) {
		cout << rank[i] << endl;
	}
	return 0;
}
题目详情
291 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

B-smooth 数

题面描述

小杨同学想寻找一种名为B-smooth 数的正整数。

如果一个正整数的最大质因子不超过B,则该正整数为B-smooth 数。

小杨同学想知道,对于给定的n和B,有多少个不超过n的B-smooth 数。

输入格式

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

输出格式

输出一个非负整数,表示不超过n的B-smooth 数的数量。


样例输入

10 3

样例输出

7

样例解释

在不超过10的正整数中,3-smooth 数有{1,2,3,4,6,8,9},共7个。

数据范围

对于全部数据,保证有1≤n≤106,1≤B≤106。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n, B;
	cin >> n >> B;
	assert(1 <= n && n <= 1e6);
	assert(1 <= B && B <= 1e6);
	vector<bool> vis = vector<bool>(n + 5, false);
	vector<int> mx_prime_factor = vector<int>(n + 5, 0);
	vector<int> prime;
	mx_prime_factor[1] = 1;
	for (int i = 2; i <= n; i ++) {
		if (! vis[i]) {
			mx_prime_factor[i] = i;
			prime.push_back(i);
		}
		for (int p : prime) {
			if (1ll * p * i > n)
				break ;
			vis[i * p] = 1;
			mx_prime_factor[i * p] = max(mx_prime_factor[i * p],max(mx_prime_factor[i], p));
			if (i % p == 0)
				break ;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i ++)
		ans += (mx_prime_factor[i] <= B);
	cout << ans;
	return 0;
}
题目详情
292 简答题 偏难 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;
}
题目详情
293 简答题 偏难 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;
}
题目详情
294 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

因数分解(2023.9C++五级)

时间限制:1.0 s

内存限制:128.0 MB

问题描述

每个正整数都可以分解成素数的乘积,例如:6=2×3、20=22×5

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

输入描述

输入第一行,包含一个正整数N。约定2≤N≤1012

输出描述

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


样例输入1

6

样例输出1

2 * 3

样例输入2

20

样例输出2

2^2 * 5

样例输入3

23

样例输出3

23

答案与解析
参考答案
#include <iostream>
using namespace std;
int main() {
	long long N = 0;
	cin >> N;
	bool first = true;
	for (long long p = 2; p * p <= N; p++) {
		if (N % p != 0)
			continue;
		int cnt = 0;
		while (N % p == 0) {
			cnt++;
			N /= p;
		}
		if (first) {
			first = false;
		} else {
			cout << " * ";
		}
		cout << p;
		if (cnt > 1)
			cout << "^" << cnt;
	}
	if (N > 1) {
		if (first) {
			first = false;
		} else {
			cout << " * ";
		}
		cout << N;
	}
	cout << endl;
	return 0;
}
题目详情
295 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

巧夺大奖(2023.9C++五级)

时间限制:1.0 s

内存限制:128.0 MB


问题描述

小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则:

1、游戏分为n个时间段,参加者每个时间段可以选择一个小游戏。

2、游戏中共有n个小游戏可供选择。

3、每个小游戏有规定的时限和奖励。对于第i个小游戏,参加者必须在第Ti个时间段结束前完成才能得到奖励Ri。

小明发现,这些小游戏都很简单,不管选择哪个小游戏,他都能在一个时间段内完成。关键问题在于,如何安排每个时间段分别选择哪个小游戏,才能使得总奖励最高?

输入描述

输入第一行,包含一个正整数n。 既是游戏时间段的个数,也是小游戏的个数。约定1≤n≤500。

输入第二行,包含n个正整数。第i个正整数为Ti,即第i个小游戏的完成期限。约定1≤Ti≤n。

输入第三行,包含n个正整数。第i个正整数为Ri,即第i个小游戏的完成奖励。约定1≤Ri≤1000。

 输出描述

输出一行,包含一个正整数C,为最高可获得的奖励。


样例输入1

7

4 2 4 3 1 4 6

70 60 50 40 30 20 10

样例输出1

230

样例解释1

7个时间段可分别安排完成第4、2、3、1、6、7、5个小游戏,其中第4、2、3、1、7个小游戏在期限内完成。因此,可以获得总计40+60+50+70+10=230的奖励。

答案与解析
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
int n = 0;
struct game_t {
	int T, R;
} games[500];
bool game_cmp(game_t x, game_t y){
	return x.R > y.R;
}
bool arrange[500];
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		arrange[i] = false;
	for (int i = 0; i < n; i++)
		cin >> games[i].T;
	for (int i = 0; i < n; i++)
		cin >> games[i].R;
	sort(games, games + n, game_cmp);
	int sum = 0;
	for (int i = 0; i < n; i++) {
		for (int t = games[i].T - 1; t >= 0; t--)
			if (!arrange[t]) {
				arrange[t] = true;
				sum += games[i].R;
				break;
			}
	}
	cout << sum << endl;
	return 0;
}
题目详情
296 简答题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

有限不循环小数

答案与解析
参考答案
#include <iostream>
 using namespace std;
 int main() {
     int l, r, ans = 0;
     cin >> l >> r;
     for(int i = l; i <= r; i++) {
         int t = i;
         while(t && t % 2 == 0)
             t /= 2;
         while(t && t % 5 == 0)
             t /= 5;
         if(t == 1)
             ans++;
     }
     cout << ans << endl;
     return 0;
 }
题目详情
297 简答题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

找数

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());
    int ans = 0;
    int b;
    for(int i = 0; i < m; i++){
        cin >> b;
        if(binary_search(a.begin(), a.end(), b)){
            ans++;
        }
    }
    cout << ans;
    return 0;
}
题目详情