গেম শোয়ে পুরস্কার লুকানোর জন্য কতগুলো রুম ব্যবহার করা যায়

একটি গেম শোতে 2n সংখ্যক রুম বৃত্তাকার আকারে সাজানো আছে। একটি রুমে পুরস্কার আছে। রুম নম্বর: ১, ২, ৩, ..., n, -n, -(n-1), ..., -১ (ক্লকওয়াইজ)। প্রতিটি রুমের দরজায় একটি মার্কিং x আছে যার মানে হলো বর্তমান রুম থেকে x দূরতিতে অন্য একটি রুম। x পজিটিভ হলে ক্লকওয়াইজ, নেগেটিভ হলে অ্যান্টি-ক্লকওয়াইজ। পার্টিসিপেন্টরা একদিক থেকে শুরু করে ঘুরে বেড়ান। কতগুলো রুমে পুরস্কার রাখলে পার্টিসিপেন্টরা সেটা খুঁজে পাবে না (অর্থাৎ সেগুলো কখনো ভিজিট হবে না) সেটা বের করতে হবে।

ইনপুট: [[4, 2]] → আউটপুট: [2]। n=4 (মোট ৮ রুম), শুরু ২ নম্বর রুম। রুম সিকোয়েন্স: ২, -৪, -১, ১, ৩, -২, -১, ১, ৩, -২... রুম ৪ এবং -৩ কখনো ভিজিট হয় না।

সমাধানের ধাপসমূহ (নম্বর থিওরি + ওয়লার টোটিয়েন্ট)

• প্রাইম নাম্বার সিভ (prime_num_find) ব্যবহার করে ফ্যাক্টরাইজেশন

• factor_finder(p): p-এর প্রাইম ফ্যাক্টরাইজেশন রিটার্ন করে

• euler_func(p): ওয়লার টোটিয়েন্ট ফাংশন φ(p) গণনা

• প্রत्यেক ইনপুট (p, q)-এর জন্য:

  • r = 2p + 1
  • r //= gcd(r, q % r)
  • t_value = euler_func(r)
  • t_value-এর প্রাইম ফ্যাক্টর দিয়ে t_value কমিয়ে আনার চেষ্টা করুন যদি 2^(t_value/value) ≡ 1 (mod r)
  • উত্তর = 2p - t_value

উদাহরণ (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]]))

ইনপুট

[[4, 2]]

আউটপুট

[2]