賞品を隠すことができる部屋の数を見つけるためのPythonプログラム

ゲーム番組で、2n個の部屋が円形に配置されているとします。ある部屋には、参加者が集めなければならない賞品があります。部屋には、1、2、3、....、n、-n、-（n-1）、....、-1の番号が付けられています。時計回りに。各部屋にはドアがあり、そのドアによって、異なる部屋を訪れることができます。すべてのドアにはxのマークが付いています。これは、別の部屋が現在の部屋からxの距離にあることを意味します。 xの値が正の場合、ドアはx番目の部屋から時計回りにその部屋に向かって開きます。 xの値が負の場合、部屋は反時計回りにx番目の部屋に開いていることを意味します。賞品を保管できる部屋の数を確認する必要があり、参加者は賞品を見つけるのが困難です。

したがって、入力がinput_array =[[4、2]]のような場合、出力は[2]

入力には2つの値があり、最初の値は部屋数の半分であるnであり、2番目の値は参加者が賞品を探し始める部屋番号です。ここでは、2x4 =8の部屋があり、参加者は時計回りに2番目の部屋から賞品を見つけ始めます。部屋には、時計回りに1、2、3、4、-4、-3、-2、-1のように番号が付けられています。参加者は次の方法で部屋を訪問し始めます：2、-4、-1、1、3、-2、-1、1、3、-2、......したがって、部屋4と-3は決して取得しません訪問した場合、賞品がこれら2つの部屋のいずれかに隠されていると、参加者はそれを見つけることができません。

これを解決するには、次の手順に従います-

• 関数prime_num_find（）を定義します。これにはn
  かかります

  • p_nums：=値2で初期化された新しいリスト

  • チェック：=要素のバイト表現を含む新しいリスト

• 3からnの範囲の値の場合、2ずつ増やします。

  • check [value]がゼロ以外の場合、
    • 次の反復に進む
  • p_numsの最後に値を挿入
  • 3 *値からnの範囲のiの場合、各ステップで2 *値ずつ更新し、
    • check [i]：=1
  • p_numsを返す
• 関数factor_finder（）を定義します。これには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
  • return 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を返す
• メインの関数/メソッドから、次の手順を実行します-
• 出力：=新しいリスト
• input_arrayの各項目について、
  を実行します。
  • p：=item [0]
  • q：=item [1]
  • r：=2 * p + 1
  • r：=（r / gcd value of（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]