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

GESP-Python五级 题库

共 23 道题 ,第 2 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 1.1 素数与合数 清除
21 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 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\*\*48=64 是 128 的因子。

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

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

答案与解析
参考答案
def calc(x):
	ans = 0
	tmp = 1
	while x >= tmp:
		ans += 1
		x -= tmp
		tmp += 1
	return ans

n = int(input())
ans = 0
i = 2

while i * i <= n:
	if n % i == 0:
		cnt = 0
		while n % i == 0:
			cnt += 1
			n //= i
		ans += calc(cnt)
	i += 1

if n != 1:
	ans += calc(1)
	
print(ans)
题目详情
22 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 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。

答案与解析
参考答案
prime = []
is_prime = [False] * 100010

def Eratosthenes(n):
	is_prime[0] = is_prime[1] = False
	for i in range(2, n + 1):
		is_prime[i] = True
	for i in range(2, n + 1):
		if is_prime[i]:
			prime.append(i)
			if i * i > n:
				continue
			for j in range(i * i, n + 1, i):
				is_prime[j] = False

Eratosthenes(100000)

t = int(input())
for _ in range(t):
	tmp = 1
	x = int(input())
	ans = 0
	while True:
		if is_prime[x]:
			ans += 1
			break
		x -= tmp
		ans += 1
		if x <= 0:
			if x < 0:
				ans = -1
			break
		tmp *= 2
	print(ans)


考虑到物理攻击一定是1,2,4,……2i−1,这样枚举的,所以魔法攻击放到什么位置其实没有影响。

所以我们考虑如果当前x是质数,直接减质数结束即可,如果不是质数的话,就使用物理攻击即可。

流程:先用质数筛求质数,然后输入t,输入x,我们需要维护当前的物理攻击的值tmp,也就是1 2 4 ……,如果当前的x是质数,则直接结束,如果不是质数,则x-=tmp。

然后进行判断,如果x==0,则结束输出答案,如果x<0,则是没有答案的情况,输出-1

题目详情
23 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 1.1 素数与合数

因数分解

时间限制: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

答案与解析
参考答案
input_number = int(input())
original_number = input_number
factors = []
def isPrime(num):
	for j in range(2, int(num**0.5)):
		if num % j == 0:
			return False
	return True
if isPrime(input_number):
	factors.append([input_number, 1])
else:
	for i in range(2, input_number+1):
		input_number = int(input_number)
		if input_number % i == 0:
			factors.append([i, 0])
			while input_number % i == 0:
				factors[-1][1] += 1
				input_number //= i
			if isPrime(input_number):
				if input_number != 1:
					factors.append([input_number, 1])
				break
for i in range(len(factors)):
	if i != 0:
		print(" * ", end="")
	if factors[i][1] == 1:
		print(factors[i][0], end="")
	else:
		print(f"{factors[i][0]}^{factors[i][1]}", end="")
print("")


题目详情