Chương trình Python tìm số phòng có thể giấu giải thưởng

Giả sử trong trò chơi có 2n phòng xếp thành vòng tròn. Trong một phòng có giải thưởng. Phòng đánh số 1,2,3,...,n,-n,-(n-1),...,-1 theo chiều kim đồng hồ. Mỗi phòng có cửa dẫn đến phòng khác. Mỗi cửa có dấu x nghĩa là phòng khác ở khoảng cách x từ phòng hiện tại. Nếu x dương: cửa mở ra phòng thứ x theo chiều kim đồng hồ. Nếu x âm: cửa mở ra phòng thứ x ngược chiều kim đồng hồ. Tìm số phòng có thể giấu giải thưởng khiến người chơi khó tìm.

Ví dụ: input_array = [[4, 2]], kết quả là [2]. Có 8 phòng, bắt đầu từ phòng 2. Người chơi sẽ đi: 2, -4, -1, 1, 3, -2, -1, 1, 3, -2... Phòng 4 và -3 không bao giờ được ghé thăm.

Giải thuật

Sử dụng số học: hàm Euler, phân tích thừa số nguyên tố, tìm chu kỳ.

1. Hàm prime_num_find(n): sàng Eratosthenes tìm số nguyên tố ≤ n
2. Hàm factor_finder(p): phân tích thừa số nguyên tố của p
3. Hàm euler_func(p): tính hàm Euler φ(p)
4. Hàm chính solve(input_array):
   • Với mỗi [p, q] trong input_array:
     • r := 2*p + 1
     • r //= gcd(r, q % r)
     • t_value := euler_func(r)
     • Với mỗi thừa số value của t_value:
       • While t_value % value == 0 và pow(2, t_value // value, r) == 1: t_value //= value
     • Thêm 2*p - t_value vào kết quả

Ví dụ

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

Input

[[4, 2]]

Output

[2]