Pythonで与えられた方程式の値を見つけるためのプログラム

5つの整数a、b、c、d、nが与えられていると仮定します。 （（ab）（cd））modnを見つける必要があります。出力値は整数です。

したがって、入力がa =2、b =3、c =2、d =4、n =10の場合、出力は6になります。

2^3 = 8
2^4 = 16
8^16 = 281474976710656
281474976710656 mod 10 = 6

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

• 関数helper（）を定義します。これにはn
  かかります
  • p：=n
  • i：=2
  • i * i <=nの間、do
    • n mod iが0と同じ場合、
      • p：=p-（p / i）のフロア値
    • n mod iは0と同じですが、
      • n：=（n / i）のフロア値
    • iが2と同じでない場合は、
      • i：=i + 2
    • それ以外の場合、
      • i：=i + 1
  • n> 1の場合、
    • p：=p-（p / n）のフロア値
  • return p
• bが0と同じまたは（cが0と同じで、dが0と同じでない）の場合、
  • return（a ^ 0）mod n
• cが1と同じか、dが0と同じ場合、
  • return（a ^ b）mod n
• aが0と同じか、mod nが0と同じ場合、
  • 0を返す
• dが1と同じ場合、
  • return（a ^ b * c）mod n
• p：=helper（n）
• e：=（c ^ d）mod p + p
• return（（（a ^ b）mod n）^ e）mod n

例

理解を深めるために、次の実装を見てみましょう-

def helper(n):
   p = n
   i = 2
   while i * i <= n:
      if n % i == 0:
         p -= p // i
      while n % i == 0:
         n = n // i
      if i != 2:
         i += 2
      else:
         i += 1
   if n > 1:
      p -= p // n
   return p

def solve(a, b, c, d, n):
   if b == 0 or (c == 0 and d != 0):
      return pow(a, 0, n)
   if c == 1 or d == 0:
      return pow(a, b, n)
   if a == 0 or a % n == 0:
      return 0
   if d == 1:
      return pow(a, b * c, n)
   p = helper(n)
   e = pow(c, d, p) + p
   return pow(pow(a, b, n), e, n)

print(solve(2, 3, 2, 4, 10))

入力

2, 3, 2, 4, 10

出力

6