โจทย์
มีห้อง 2n ห้องเรียงวงกลม หมายเลข 1..n, -n..-1 ตามเข็มนาฬิกา แต่ละห้องมีประตูไปห้องอื่น ระยะ x (บวก=ตามเข็ม, ลบ=ทวนเข็ม) หาจำนวนห้องที่ถ้าวางรางวัลจะหาไม่เจอ (Participant เดินวนไปเรื่อยๆ)
ตัวอย่าง: input_array = [[4, 2]] (n=4, เริ่มห้อง 2) → Output: [2] (ห้อง 4 และ -3 ไม่ถูกเยี่ยมชม)
อัลกอริธึม (Number Theory: Euler's Totient, Order of 2)
- คำนวณ
r = 2p+1ลดรูปด้วย GCD - หา Euler's Totient φ(r)
- หา Order ของ 2 modulo r (ค่า t น้อยที่สุดที่ 2^t ≡ 1 mod r)
- คำตอบ = 2p - t
โค้ด Python
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]])) # Output: [2]
Input / Output
Input: [[4, 2]]
Output: [2]
