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

GESP-Python五级 题库

共 173 道题 ,第 9 / 9 页 · 按题型筛选,点「查看答案」核对解析
章节 1 初等数论 清除
161 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 1.1 素数与合数

原根判断

题目描述

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

·1<g<p

·gp-1 mod p=1

·对于任意1≤i<p-1 均有 gi mod p≠1。

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

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

输入格式

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

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

输出格式

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


输入样例

3
3 998244353
5 998244353
7 998244353

输出样例

Yes
Yes
No

数据范围

对于 40% 的测试点,保证3≤p≤103 。

对于所有测试点,保证1≤T≤20 ,3≤p≤109,1<a<p ,p为质数。

答案与解析
参考答案
def fpw(b, e, p):
	if e == 0:
		return 1
	r = fpw(b, e >> 1, p)
	return r * r * (b if e & 1 else 1) % p

def solve():
	a, p = map(int, input().split())
	phi, v = p - 1, p - 1
	for i in range(2, int(phi ** 0.5) + 2):
		if v % i == 0:
			while v % i == 0:
				v //= i
			if fpw(a, phi // i, p) == 1:
				print("No")
				return
	if v > 1:
		if fpw(a, phi // v, p) == 1:
			print("No")
			return
	print("Yes")

[solve() for _ in range(int(input()))]
题目详情
162 简答题 偏难 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)
题目详情
163 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 综合练习

武器强化

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

答案与解析
参考答案
def calc(aim, n, cnt, cs):
	cur_cnt = cnt[0]
	res = 0
	tmp = []
	for i in range(1, n):
		buy = max(len(cs[i]) - aim + 1, 0)
		for j in range(buy):
			res += cs[i][j]
		cur_cnt += buy
		for j in range(buy, len(cs[i])):
			tmp.append(cs[i][j])
			
	tmp.sort()
	for i in range(aim - cur_cnt):
		res += tmp[i]
	return res
	
n, m = map(int, input().split())
cnt = [0] * n
cs = [[] for _ in range(n)]

for _ in range(m):
	p, c = map(int, input().split())
	cnt[p - 1] += 1
	cs[p - 1].append(c)
	
for i in range(n):
	cs[i].sort()
	
ans = 1000000000000000000
for i in range(max(cnt[0], 1), m + 1):
	ans = min(ans, calc(i, n, cnt, cs))
	
print(ans)
题目详情
164 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 综合练习

小杨的武器

时间限制:1.0 s

内存限制:512.0 MB

题面描述

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

小杨会依次参加m场战斗,每场战斗小杨只能且必须选择一种武器使用,假设小杨使用了第i种武器参加了第j场战斗,战斗前该武器的熟练度为ci′,则战斗后小杨对该武器的熟练度会变为ci′+a。需要注意的是,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。

答案与解析
参考答案
N = 100010

a = [0] * N
c = [0] * N

n, m = map(int, input().split())
mx = -10000
s = input().split()
for i in range(1, n + 1):
	c[i] = int(s[i-1])
	mx = max(mx, c[i])
s = input().split()
for i in range(1, m + 1):
	a[i] = int(s[i-1])
	
for i in range(1, m + 1):
	if n == 1 or a[i] > 0:
		mx += a[i]
		
print(mx)

我们想让武器熟练度最大值尽可能大,所以我们可以贪心考虑把原本的最大值,加上所有的正的熟练度,这样他就会变得最大。

流程:读入n和m,然后读入一个字符串,这个字符串就是c的信息,我们转成int类型,并找出其中的最大值mx,然后再读入一个字符串,这个字符串就是a的信息,我们把这个字符串转成int类型,判断a数组,如果当前熟练度增加值为正数,则累加到最大值mx上。

特别的,如果n==1,也就是只有一个武器,所以每次只能用这一个,这种情况下即使是负数,也要累加上。

题目详情
165 简答题 偏难 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

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

黑白格

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

答案与解析
参考答案
N = 110
w = [[0] * N for _ in range(N)]
sum_w = [[0] * N for _ in range(N)]

def main():
	n, m, k = map(int, input().split())
	for i in range(1, n+1):
		s = input()
		for j in range(1, m+1):
			w[i][j] = int(s[j-1])
			sum_w[i][j] = sum_w[i][j-1] + w[i][j]
	
	ans = 0
	for i in range(1, m+1):
		for j in range(i, m+1):
			num = []
			now = 0
			for l in range(1, n+1):
				tmp = sum_w[l][j] - sum_w[l][i-1]
				now += tmp
				num.append(now)
				if now >= k:
					if ans == 0:
						ans = (j-i+1) * l
					else:
						ans = min(ans, (j-i+1) * l)
					L, R = 1, l
					while L < R:
						mid = (L + R + 1) // 2
						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))
	print(ans)

if __name__ == "__main__":
	main()

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

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

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

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

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

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

小杨的幸运数字

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

答案与解析
参考答案
N = 10**5 + 10
a = [0] * N

def calc(x):
	i = 2
	mp = {}
	while i * i <= x:
		if x % i == 0:
			mp[i]=1
			while x % i == 0:
				x //= i
		i += 1
	if x != 1:
		mp[x]=1
	return int(len(mp.items()))

def main():
	n = int(input())
	
	for i in range(1, n + 1):
		a[i] = int(input())
		x = calc(a[i])
		if x == 2:
			print("1")
		else:
			print("0")

if __name__ == "__main__":
main()

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

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

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

成绩排序

问题描述

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

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

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

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

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

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

输入描述

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

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

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

输出描述

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

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

特别提醒

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


样例输入

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

样例输出

1
3
4
4
2
6

数据规模

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

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

答案与解析
参考答案
N = int(input())
students = []
for i in range(N):
	c, m, e = list(map(int, input().split()))
	students.append((c + m + e, c + m, max(c, m), i))
students.sort(reverse = True)
rank = [None for i in range(N)]
last_student = None
for i, student in enumerate(students):
	if student[:-1] != last_student:
		last_student = student[:-1]
		curr_rank = i + 1
	rank[student[-1]] = curr_rank
for r in rank:
	print(r)
题目详情
169 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 综合练习

B-smooth数(python)

题面描述

小杨同学想寻找一种名为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。

答案与解析
参考答案
n, B = map(int, input().split())
is_prime = [True] * (n + 1)
primes = []
max_prime_factor = [0] * (n + 1)
for i in range(2, n + 1):
	if is_prime[i]:
		primes.append(i)
		max_prime_factor[i] = i
	for p in primes:
		if i * p > n:
			break
		is_prime[i * p] = False
		max_prime_factor[i * p] = max(max_prime_factor[i], p)
		if i % p == 0:
			break
cnt = 0
for i in range(1, n + 1):
	if max_prime_factor[i] <= B:
		cnt += 1
print(cnt)
题目详情
170 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 1.3 同余与模运算

小杨的幸运数

时间限制:5.0 s

内存限制:128.0 MB

问题描述

小杨认为,所有大于等于a的完全平方数都是他的超级幸运数。

小杨还认为,所有超级幸运数的倍数都是他的幸运数。自然地,小杨的所有超级幸运数也都是幸运数。

对于一个非幸运数,小杨规定,可以将它一直+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。

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。

答案与解析
参考答案
a, n = input().split()
a, n = int(a), int(n)

max_lucky = 1001 ** 2 + 10

is_lucky = [False for i in range(max_lucky + 1)]
next_lucky = [-1 for i in range(max_lucky + 1)]
for i in range(1, max_lucky):
	if i >= a and int(i ** 0.5) ** 2 == i:
		is_lucky[i] = True
		for j in range(i + i, max_lucky, i):
			is_lucky[j] = True
for i in range(max_lucky - 1, 0, -1):
	if is_lucky[i]:
		next_lucky[i] = i
	else:
		next_lucky[i] = next_lucky[i + 1]
for i in range(n):
	x = int(input())
	assert 1 <= x <= 10 ** 6 + 1
	if next_lucky[x] == x:
		print("lucky")
	else:
		print(next_lucky[x])
题目详情
171 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 1.3 同余与模运算

烹饪问题

时间限制:1.0 s

内存限制:128.0 MB

问题描述

有N种食材,编号从0至N-1,其中第i种食材的美味度为ai。

不同食材之间的组合可能产生奇妙的化学反应。具体来说,如果两种食材的美味度分别为x和y,那么它们的契合度为x and y。

其中,and运算为按位与运算,需要先将两个运算数转换为二进制,然后在高位补足0,再逐位进行与运算。例如,12与6的二进制表示分别为 1100 和 0110 ,将它们逐位进行与运算,得到 0100 ,转换为十进制得到4,因此12 and 6=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。

答案与解析
参考答案
n = int(input())
a = list(map(int, input().split()))
a = [0] + a

def sort_(l, r, k):
	while l <= r:
		while (l <= r) and (a[l] >> k & 1):
			l += 1
		while (l <= r) and (not (a[r] >> k & 1)):
			r -= 1
		if l <= r:
			a[l], a[r] = a[r], a[l]
			l += 1
			r -= 1
	return r
ans = 0
for i in range(31, -1, -1):
	j = sort_(1, n, i)
	if j >= 2:
		ans |= 1 << i
		n = j
print(ans)
题目详情
172 简答题 偏难 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("")


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

巧夺大奖

时间限制: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的奖励。

答案与解析
参考答案
total_segements = int(input())
limits = []
rewards = []
s_limits = input()
s_limits = s_limits.split(' ')
s_rewards = input()
s_rewards = s_rewards.split(" ")
for item in s_limits:
	limits.append(int(item))
for item in s_rewards:
	rewards.append(int(item))
games = []
for i in range(len(s_limits)):
	# 结束时间,奖励值,是否可以选,是否选过
	games.append([limits[i], rewards[i], False, False])

def check_chooseable(states, current):
	for item in states:
		if item[0] >= current:
			item[2] = True
def get_current_max(states, current):
	maximum = 0
	chosen = None
	for i in range(len(states)):
		if states[i][2] and not states[i][3]:
			if maximum < states[i][1]:
				#print(states[i][1])
				maximum = max(states[i][1], maximum)
				chosen = i
	if chosen is not None:
		states[chosen][3] = True
	return maximum
total = 0
#print(games)
for t in range(total_segements, 0, -1):
	#print(t)
	check_chooseable(games, t)
	total += get_current_max(games, t)
	#print(games)
print(total)


题目详情