找出可以隐藏奖品的房间数量的 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 math def 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]