GESP C++ 五级真题（2025年3月）题解

也就是说我们要将 1 到 p−1 划分成若干段长度相同的循环周期，在 [1,p−1) 中，只有每小段的末尾，也就是 p−1 的因数的倍数，可能满足 aimodp=1。解析：注意，这里是将p的“值”设为p->next的值，不是将p=p->next。又知道 p−1 的一个因数 x，使得 axmodp=1，那么，这个因数的任意一个倍数 y，也都满足 aymodp=1。因为 ap−1modp=1 我们提

xiaohang0007

1419人浏览 · 2025-06-27 15:24:31

xiaohang0007 · 2025-06-27 15:24:31 发布

题目：https://gesp.ccf.org.cn/101/attach/1684804529553440.pdf

选择题：

1.答案：A

解析：链表需要循序访问，不能随机访问任何一个元素。

2.答案：A

解析：一眼就不对，p->next->prev原来指向p，现在指向p->next，就是自己。P->prev->next原来指向p，现在指向p->prev，也是自己。所以链断了。

3.答案：B

解析：A，head的前驱不需要赋值；C，tail的后驱不需要赋值；D，tail没有连上head

4.答案：B

解析：代入即可

5.答案：D

解析：唯一分解定理，每一项都是质因数

6.答案：C

解析：把当前所有小于n的i的倍数都设为不是质数

7.答案：A

解析：递归时函数的参数和结果保存在“栈”中。

8.答案：D

解析：factorialB不是递归

9.答案：A

解析：选择排序在交换时，可能会把后面的相等元素移动到前面，破坏原始顺序

10.答案：B

解析：1.由于i=low-1,所以要先i++;2.由于基准是每段的末尾，所以先要把小于基准的数堆到当前分段的前部。

11.答案：C

解析：⌈log2100⌉=7，向上取整

12.答案：A

解析：避免整数溢出：(left + right) 在 left 和 right 很大时可能溢出，但 left + (right - left) / 2 不会。等价于 (left + right) / 2，但更安全。

13.答案：A

解析：贪心的核心是先选择，选择当前最优解，但贪心不是一定能找到最优解。

14.答案：D

解析：首先排除A，然后排除C，return 0不可能获得最大值，且还return leftMax*rightMax，就更不符合逻辑。最后排除B，return leftMax+rightMax不符合逻辑。

15.答案：B

解析：carry是上一位的进位值，所以选B

判断题：

1.答案：T

解析：注意，这里是将p的“值”设为p->next的值，不是将p=p->next。是p.val=p->next->val。

2.答案：F

解析：链表中的存储单元是动态分配的，不需要连续。

3.答案：T

解析：如题所述。

4.答案：F

解析：贪心做的的最有选择，不一定是最优解。

5.答案：T

解析：如题所述。

6.答案：F

解析：快排平均复杂度为为O(nlogn)，最差为O（n2）

7.答案：T

解析：如题所述。

8.答案：F

解析：只适用于有序数组

9.答案：F

解析：贪心

10.答案：T

解析：如题所述。

编程题：

思路

首先，我们假设所有物品全部卖给小 B，则收入为 ∑i=12nbi。

而第 i 件物品从卖给小 B 变成卖给小 C 对收入的贡献为 ci−bi。

所以我们只需对 ci−bi 进行排序，选出前 n 个最大的，求和并加上全部卖给小 B 的收入即可。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,b[200005],c,a[200005],ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=0;i<n*2;i++) cin>>b[i],ans+=b[i];  //全部卖给小 B 的收入
    for(int i=0;i<n*2;i++) cin>>c,a[i]=c-b[i];   //记录第 i 件物品对答案的贡献
	sort(a,a+n*2,greater<long long>());          //从大到小排序
	for(int i=0;i<n;i++) ans+=a[i];              //更新答案
	cout<<ans;
    return 0; 
}

题意：

对于质数 p 而言，p 的原根 g 是满足以下条件的正整数：

1<g<p；
gp−1modp=1；
对于任意 1≤i<p−1 均有 gimodp=1。

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

给出一个整数 a 和质数 p，判断 a 是不是 p 的原根。

保证 1≤T≤20，3≤p≤109，1<a<p，p 为质数。

思路：

要想让 a 是 p 的原根，必须满足三个条件：

1<a<p ，这条已被约束条件满足了，无需判断；
ap−1modp=1，写个快速幂，O(logn) 就能判断；
对于任意 1≤i<p−1 均有 aimodp=1，如何判断？

枚举每个 i，依次用快速幂判断，但还是慢了。

正难则反，只需要知道 aimodp=1 的结果，就知道 aimodp=1。

在 [1,p−1) 中，那个 i 可能满足 aimodp=1?

假设 akmodp=1。

∴akmodp=1,ak+1modp=a,ak+2modp=a2modp,…a2kmodp=1,…a3kmodp=1,…axkmodp=1x∈[0,∞]

wow，有周期，每 k 个一循环，每个循环周期大小相等！

因为 ap−1modp=1 我们提前判段为错误，并退出了，所以现在的 a 和 p 一定满足 ap−1modp=1。

诶，我们忽略了 0，a0modp=1！

也就是说我们要将 1 到 p−1 划分成若干段长度相同的循环周期，在 [1,p−1) 中，只有每小段的末尾，也就是 p−1 的因数的倍数，可能满足 aimodp=1。

又知道 p−1 的一个因数 x，使得 axmodp=1，那么，这个因数的任意一个倍数 y，也都满足 aymodp=1。

所以只用找 p−1 的每一个因数 x 是否满足 axmodp=1，就可以推出"对于任意 1≤i<p−1 均有 aimodp=1"这个条件了

代码

#include<iostream>
#include<vector>
#define ll long long
using namespace std;
vector<ll>yin;       //表示p-1的因数
ll fpow(ll a,ll b,ll p){//快速幂
	a%=p;
	if(b==1)return a;
	if(b==0)return 1;
	if(b&1)return a*fpow(a*a%p,(b>>1),p)%p;
	return fpow(a*a%p,(b>>1),p);
}
void find_yin(ll x){	//找因数
	while(yin.size())   //清空
		yin.pop_back();    
	for(ll i=2;i*i<=x;i++){
		if(x%i==0){
			yin.push_back(i);
			yin.push_back(x/i);
		}
	}
	return ;
}
void doing(){//求出每次答案
	ll p,a;
	cin>>a>>p;
	if(fpow(a,p-1,p)!=1){  //条件2
		puts("No");
		return ;
	}
	find_yin(p-1);         //找p-1的因数
	for(int i=0;i<yin.size();i++){
		ll y=yin[i];       //枚举每个因数
		if(fpow(a,y,p)==1){//满足条件4(不满足条件3)
			puts("No");
			return ;
		}
	}
	puts("Yes");
	return ;
}
int main(){
	int t; 
	cin>>t;
	while(t--){
		doing();
	}
	return 0;
}