Python程式：計算給定方程的值

假設我們得到五個整數a、b、c、d、n。我們需要計算((ab)(cd)) mod n。輸出值為一個整數。

因此，如果輸入為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 時，執行以下操作：
      • 如果 n mod i 等於 0，則
        • p := p - floor(p / i)
      • 當 n mod i 等於 0 時，執行以下操作：
        • n := floor(n / i)
      • 如果 i 不等於 2，則
        • i := i + 2
      • 否則，
        • i := i + 1
    • 如果 n > 1，則
      • p := p - floor(p / n)
    • 返回 p
  • 如果 b 等於 0 或 (c 等於 0 且 d 不等於 0)，則
    • 返回 (a ^ 0) mod n
  • 如果 c 等於 1 或 d 等於 0，則
    • 返回 (a ^ b) mod n
  • 如果 a 等於 0 或 a mod n 等於 0，則
    • 返回 0
  • 如果 d 等於 1，則
    • 返回 (a ^ b * c) mod n
  • p := helper(n)
  • e := (c ^ d) mod p + p
  • 返回 (((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

更新於： 2021年10月20日

933 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告