पायथन प्रोग्राम उन कमरों की संख्या का पता लगाने के लिए जिनमें पुरस्कार छिपाया जा सकता है

मान लीजिए, एक गेम शो में 2n संख्या में कमरे हैं जो एक सर्कल में व्यवस्थित हैं। एक कमरे में, एक पुरस्कार है जिसे प्रतिभागियों को इकट्ठा करना होता है। कमरों की संख्या 1, 2, 3,...., n, -n, -(n-1),...., -1 से है। एक दक्षिणावर्त तरीके से। प्रत्येक कमरे में एक दरवाजा होता है और उस दरवाजे से एक अलग कमरे में जाया जा सकता है। प्रत्येक दरवाजे पर एक अंकन x है, जिसका अर्थ है कि दूसरा कमरा वर्तमान कमरे से x की दूरी पर स्थित है। यदि x का मान धनात्मक है, तो उस कमरे से दक्षिणावर्त दिशा में xवें कमरे का दरवाजा खुलता है। यदि x का मान ऋणात्मक है, तो इसका अर्थ है कि कमरा xवें कमरे में वामावर्त दिशा में खुलता है। हमें उन कमरों की संख्या ज्ञात करनी है जिनमें पुरस्कार रखा जा सकता है और प्रतिभागियों को पुरस्कार खोजने में कठिनाई होती है।

इसलिए, यदि इनपुट input_array =[[4, 2]] जैसा है, तो आउटपुट [2]

होगा।

इनपुट में दो मान होते हैं, पहला मान n है जो कमरों की संख्या का आधा है, और दूसरा मान वह कमरा नंबर है जहां प्रतिभागी पुरस्कार के लिए खोजना शुरू करते हैं। यहां, 2x4 =8 कमरे हैं और प्रतिभागी दूसरे कमरे से दक्षिणावर्त दिशा में पुरस्कार ढूंढना शुरू करते हैं। कमरों को घड़ी की दिशा में 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 के अंत में मान डालें
- i श्रेणी में 3 * मान से n तक, प्रत्येक चरण में 2 * मान से अपडेट करें, करें
  - जांचें[i] :=1
- p_nums लौटाएं
फ़ंक्शन फ़ैक्टर_फ़ाइंडर () को परिभाषित करें। इसमें p
- p_nums :=prime_num_find(45000)
- f_nums :=एक नया नक्शा
p_nums में प्रत्येक मान के लिए, करें
- यदि मान * मान> p शून्य नहीं है, तो
  - लूप से बाहर आएं
- जबकि p mod मान 0 के समान है, करें
  - 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 / 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]