Chương trình Python để tìm ra số lượng phòng có thể ẩn giải thưởng

Giả sử, trong một game show có 2n số phòng được xếp thành hình tròn. Ở một trong các phòng, có một giải thưởng mà những người tham gia phải thu thập. Các phòng được đánh số từ 1, 2, 3, ...., n, -n, - (n - 1), ...., -1. theo chiều kim đồng hồ. Mỗi phòng đều có một cánh cửa và bằng cánh cửa đó, một phòng khác có thể được vào thăm. Mọi cánh cửa đều có đánh dấu x trên đó, có nghĩa là một phòng khác nằm cách phòng hiện tại một khoảng x. Nếu giá trị của x là dương thì cửa mở vào phòng thứ x theo chiều kim đồng hồ từ phòng đó. Nếu giá trị của x là âm, thì có nghĩa là căn phòng mở ra căn phòng thứ x theo hướng ngược chiều kim đồng hồ. Chúng tôi phải tìm ra số lượng phòng có thể giữ giải thưởng và những người tham gia gặp khó khăn trong việc tìm kiếm giải thưởng.

Vì vậy, nếu đầu vào giống như input_array =[[4, 2]], thì đầu ra sẽ là [2]

Đầu vào có hai giá trị, giá trị đầu tiên là n bằng một nửa số phòng và giá trị thứ hai là số phòng mà người tham gia bắt đầu tìm kiếm giải thưởng. Tại đây có 2x4 =8 phòng và người tham gia bắt đầu tìm giải thưởng từ phòng thứ 2 theo chiều kim đồng hồ. Các phòng được đánh số như vậy theo chiều kim đồng hồ 1, 2, 3, 4, -4, -3, -2, -1. Những người tham gia sẽ bắt đầu tham quan các phòng theo cách sau:2, -4, -1, 1, 3, -2, -1, 1, 3, -2, ...... Vì vậy, các phòng 4 và -3 không bao giờ nhận được đã truy cập, nếu giải thưởng được giấu trong một trong hai phòng này thì người tham gia không thể tìm thấy.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Định nghĩa một hàm prime_num_find (). Điều này sẽ mất n
- p_nums:=một danh sách mới được khởi tạo với giá trị 2
- check:=một danh sách mới chứa các biểu diễn byte của các phần tử
cho giá trị trong phạm vi 3 đến n, tăng 2, thực hiện
- nếu kiểm tra [giá trị] khác 0, thì
  - chuyển sang lần lặp tiếp theo
- chèn giá trị vào cuối p_nums
- đối với tôi trong phạm vi 3 * giá trị đến n, cập nhật từng bước theo giá trị 2 *, thực hiện
  - kiểm tra [i]:=1
- trả về p_nums
Xác định hàm factor_finder (). Điều này sẽ mất p
- p_nums:=prime_num_find (45000)
- f_nums:=một bản đồ mới
đối với mỗi giá trị trong p_nums, thực hiện
- nếu value * value> p khác 0, thì
  - ra khỏi vòng lặp
- trong khi giá trị p mod giống như 0, hãy thực hiện
  - p:=giá trị sàn của (p / value)
  - nếu giá trị bằng f_nums, thì
    - f_nums [value]:=f_nums [value] + 1
  - khác,
    - f_nums [value]:=0
nếu p> 1, thì
- f_nums [p]:=1
- trả về f_nums
Xác định một hàm euler_func (). Điều này sẽ mất p
- f_nums:=factor_finder (p)
- t_value:=1
đối với mỗi giá trị trong f_nums, thực hiện
- t_value:=t_value * ((value-1) * value ^ (f_nums [value] - 1))
  - trả về t_value
Từ hàm / phương thức chính, hãy thực hiện như sau -
output:=một danh sách mới
đối với mỗi mục trong input_array, hãy thực hiện
- p:=item [0]
- q:=item [1]
- r:=2 * p + 1
- r:=giá trị sàn của (giá trị r / gcd của (r, q mod r))
- t_value:=euler_func (r)
- đối với mỗi giá trị trong factor_finder (t_value), hãy thực hiện
  - trong khi giá trị của mod t_value giống 0 và (2 ^ giá trị tầng của (t_value / value) mod r) giống với 1, do
    - t_value:=giá trị sàn của (t_value / value)
- chèn 2 * p - t_value vào cuối đầu ra
trả về kết quả đầu ra

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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]]))

Đầu vào

[[4, 2]]

Đầu ra

[2]