পাইথন প্রোগ্রাম যে কয়টি ঘরের মধ্যে একটি পুরস্কার লুকানো যেতে পারে তা খুঁজে বের করতে

ধরুন, একটি গেম শোতে একটি বৃত্তে সাজানো 2n সংখ্যক কক্ষ রয়েছে। একটি কক্ষে, একটি পুরস্কার রয়েছে যা অংশগ্রহণকারীদের সংগ্রহ করতে হবে। কক্ষগুলি 1, 2, 3, ...., n, -n, -(n - 1), ...., -1 থেকে সংখ্যাযুক্ত। ঘড়ির কাঁটার দিকে প্রতিটি ঘরে একটি দরজা রয়েছে এবং সেই দরজা দিয়ে, একটি আলাদা কক্ষ পরিদর্শন করা যেতে পারে। প্রতিটি দরজায় একটি x চিহ্ন রয়েছে, যার অর্থ বর্তমান ঘর থেকে x এর দূরত্বে অন্য একটি রুম অবস্থিত। যদি x-এর মান ধনাত্মক হয়, তাহলে দরজাটি সেই ঘর থেকে ঘড়ির কাঁটার দিকে xth ঘরে খোলে। যদি x-এর মান ঋণাত্মক হয়, তাহলে এর অর্থ হল ঘরটি ঘড়ির কাঁটার বিপরীত দিকে xতম ঘরে খোলে। আমাদের খুঁজে বের করতে হবে কয়টি কক্ষে পুরস্কার রাখা যায় এবং অংশগ্রহণকারীদের পুরস্কার খুঁজে পেতে অসুবিধা হয়।

সুতরাং, যদি ইনপুটটি হয় input_array =[[4, 2]], তাহলে আউটপুট হবে [2]

ইনপুটটির দুটি মান রয়েছে, প্রথম মানটি হল n যা কক্ষের সংখ্যার অর্ধেক, এবং দ্বিতীয় মানটি হল রুম নম্বর যেখানে অংশগ্রহণকারীরা পুরস্কারের জন্য খুঁজে পেতে শুরু করে৷ এখানে, 2x4 =8টি কক্ষ রয়েছে এবং অংশগ্রহণকারীরা ঘড়ির কাঁটার দিকে 2য় কক্ষ থেকে পুরস্কার খুঁজে পেতে শুরু করে। ঘরগুলিকে ঘড়ির কাঁটার দিকে 1, 2, 3, 4, -4, -3, -2, -1 অনুসারে নম্বর দেওয়া হয়েছে। অংশগ্রহণকারীরা এই পদ্ধতিতে কক্ষগুলি পরিদর্শন করা শুরু করবে:2, -4, -1, 1, 3, -2, -1, 1, 3, -2, ...... সুতরাং 4 এবং -3 রুমগুলি কখনই পাবে না পরিদর্শন করেছেন, যদি পুরস্কারটি এই দুটি কক্ষের একটিতে লুকিয়ে থাকে তাহলে অংশগ্রহণকারীরা এটি খুঁজে পাবে না।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সংজ্ঞায়িত করুন prime_num_find()। এটি n
  লাগবে

  • p_nums :=মান 2 সহ একটি নতুন তালিকা শুরু করা হয়েছে

  • চেক :=উপাদানগুলির বাইট উপস্থাপনা সম্বলিত একটি নতুন তালিকা

• 3 থেকে n রেঞ্জের মানের জন্য, 2 দ্বারা বাড়ান, করুন

  • যদি চেক[মান] অ-শূন্য হয়, তাহলে
    • পরবর্তী পুনরাবৃত্তির জন্য যান
  • p_nums-এর শেষে মান সন্নিবেশ করান
  • আমি পরিসীমা 3 * মান থেকে n পর্যন্ত, প্রতিটি ধাপে 2 * মান দ্বারা আপডেট করুন, করুন
    • চেক[i] :=1
  • p_nums ফেরত দিন
• একটি ফাংশন ফ্যাক্টর_ফাইন্ডার() সংজ্ঞায়িত করুন। এটি p
  লাগবে
  • p_nums :=prime_num_find(45000)
  • f_nums :=একটি নতুন মানচিত্র
• p_nums-এ প্রতিটি মানের জন্য, করুন
  • যদি মান * মান> p অ-শূন্য হয়, তাহলে
    • লুপ থেকে বেরিয়ে আসুন
  • যদিও p mod এর মান 0 এর মত, do
    • p :=(p / মান) এর ফ্লোর মান
    • যদি মান f_nums-এ থাকে, তাহলে
      • f_nums[value] :=f_nums[value] + 1
    • অন্যথায়,
      • f_nums[value] :=0
• যদি p> 1, তারপর
  • f_nums[p] :=1
  • f_nums ফেরত দিন
• একটি ফাংশন euler_func() সংজ্ঞায়িত করুন। এটি p
  লাগবে
  • f_nums :=factor_finder(p)
  • t_value :=1
• f_nums-এ প্রতিটি মানের জন্য, করুন
  • t_value :=t_value * (value-1) * value^(f_nums[value] - 1))
    • t_value ফেরত দিন
• প্রধান ফাংশন/পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
• আউটপুট :=একটি নতুন তালিকা
• ইনপুট_অ্যারেতে প্রতিটি আইটেমের জন্য, করুন
  • p :=আইটেম[0]
  • q :=আইটেম[1]
  • r :=2 * p + 1
  • r :=(r / gcd এর মান (r, q mod r)) এর ফ্লোর মান
  • t_value :=euler_func(r)
  • factor_finder(t_value) এ প্রতিটি মানের জন্য
    করুন
    • যদিও t_value mod এর মান 0 এর সমান এবং (2^ ফ্লোর এর মান (t_value / value) mod r) 1 এর সমান, do
      • t_value :=(t_value / মান)
      এর তল মান
  • আউটপুটের শেষে 2 * p - t_value সন্নিবেশ করুন
• রিটার্ন আউটপুট

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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]