找出可以隐藏奖品的房间数量的 Python 程序
假设在一个游戏节目中，有 2n 个房间排列成一个圆圈。在其中一个房间里，有一个参与者必须收集的奖品。房间编号为 1, 2, 3,...., n, -n, -(n - 1),...., -1。以顺时针方式。每个房间都有一扇门，通过那扇门，可以访问不同的房间。每扇门上都有一个标记 x，这意味着另一个房间与当前房间的距离为 x。如果 x 的值为正，则门从该房间顺时针方向打开到第 x 个房间。如果 x 的值为负，则表示该房间向逆时针方向的第 x 个房间开放。我们必须找出可以存放奖品的房间数量，参与者很难找到奖品。
因此，如果输入类似于 input_array = [[4, 2]]，那么输出将是 [2]
输入有两个值，第一个值是 n，它是房间数的一半，第二个值是参与者开始寻找奖品的房间号。这里有 2x4 = 8 个房间，参与者从顺时针方向的第二个房间开始寻找奖品。房间按顺时针方向编号为 1、2、3、4、-4、-3、-2、-1。参与者将以这种方式开始访问房间：2, -4, -1, 1, 3, -2, -1, 1, 3, -2, ...... 所以房间 4 和 -3 永远不会得到参观过，如果奖品藏在这两个房间之一，那么参与者就找不到它。
示例
让我们看看以下实现以获得更好的理解 -
import mathdef prime_num_find(n):
p_nums = [2]
check = bytearray(n)
for value in range(3, n, 2):
if check[value]:
continue
p_nums.append(value)
for i in range(3 * value, n, 2 * value):
check[i] = 1
return p_nums
def factor_finder(p):
p_nums = prime_num_find(45000)
f_nums = {}
for value in p_nums:
if value * value > p:
break
while p % value == 0:
p //= value
f_nums[value] = f_nums.get(value,0) + 1
if p > 1:
f_nums[p] = 1
return f_nums
def euler_func(p):
f_nums = factor_finder(p)
t_value = 1
for value in f_nums:
t_value *= (value-1) * value ** (f_nums[value]-1)
return t_value
def solve(input_array):
output = []
for item in input_array:
p, q = item[0], item[1]
r = 2 * p + 1
r //= math.gcd(r, q % r)
t_value = euler_func(r)
for value in factor_finder(t_value):
while t_value % value == 0 and pow(2, t_value // value, r) == 1:
t_value //= value
output.append(2 * p - t_value)
return output
print(solve([[4, 2]]))
输入
[[4, 2]]输出结果
[2]
以上是 找出可以隐藏奖品的房间数量的 Python 程序 的全部内容， 来源链接： utcz.com/z/360586.html
