首页 › 题库 › GESP编程能力等级认证 › 1.1 素数与合数

GESP-C++五级 题库

共 35 道题 ,第 2 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 1.1 素数与合数 清除
21 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

线性筛相对于埃拉托斯特尼筛法,每个合数只会被它的最小质因数筛去一次,因此效率更高。

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

任何一个大于1的自然数都可以分解成若干个不同的质数的乘积,且分解方式是唯一的。(2024.12-5)

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

找出自然数 n 以内的所有质数,常用算法有埃拉托斯特尼(埃氏)筛法和线性筛法,其中线性筛法效率更高。

A
对
B
错
答案与解析
正确答案:对

常见的质数筛有埃氏筛和欧拉筛(线性筛法),其中埃氏筛的时间复杂度为O(nlogn),经过一定的优化,可以到O(nloglogn),欧拉筛的时间复杂度为O(n),大部分情况下,欧拉筛的效率更高。

题目详情
24 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

唯一分解定理表明任何一个大于 1 的整数都可以唯一地分解为素数之和。

A
对
B
错
答案与解析
正确答案:错

任何一个大于等于2的整数,都可以唯一的分解为若干个质数的幂次方的乘积的形式

题目详情
25 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

找出自然数n以内的所有质数,常用算法有埃拉托斯特尼(埃氏)筛法和线性筛法,其中埃氏筛法效率更高。

A
对
B
错
答案与解析
正确答案:错

埃氏筛法是一种简单直观的质数筛选算法,适用于较小范围内的质数查找,随着 n 的增大,其效率会下降,因为需要标记的倍数越多。线性筛法是在埃氏筛法基础上的改进,效率更高。

题目详情
26 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

唯一分解定理表明任何一个大于1的整数都可以唯一地表示为一系列质数的乘积,即质因数分解是唯一的。

A
对
B
错
答案与解析
正确答案:对

一个整数可以有多种因数分解的方式(比如顺序不同),但其包含的质数因子及其指数是唯一确定的。

题目详情
27 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

素数表的埃氏筛法和线性筛法的时间复杂度都是O(NloglogN)。(   )

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

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

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

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

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

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

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
31 简答题 偏难 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;
}
题目详情
32 简答题 偏难 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;
}
题目详情
33 简答题 偏难 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";
}
题目详情
34 简答题 偏难 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";
	}
}
题目详情
35 简答题 偏难 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;
}
题目详情