โปรแกรมหาค่าของสมการที่กำหนดใน 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
- ผม :=2
- ในขณะที่ i * i <=n ทำ
  - ถ้า n mod i เหมือนกับ 0 แล้ว
    - p :=p - ค่าพื้นของ (p / i)
  - ในขณะที่ n mod i เหมือนกับ 0, do
    - n :=ค่าพื้นของ (n / i)
  - ถ้าฉันไม่เหมือน 2 แล้ว
    - ผม :=ผม + 2
  - มิฉะนั้น
    - ผม :=ผม + 1
- ถ้า n> 1 แล้ว
  - p :=p - ค่าพื้นของ (p / n)
- คืนสินค้า
ถ้า b เหมือนกับ 0 หรือ (c เหมือนกับ 0 และ d ไม่เหมือนกับ 0) แล้ว
- กลับ (a ^ 0) mod n
ถ้า c เหมือนกับ 1 หรือ d เหมือนกับ 0 แล้ว
- กลับ (a ^ b) mod n
ถ้า a เหมือนกับ 0 หรือ mod n เหมือนกับ 0 แล้ว
- คืน 0
ถ้า d เหมือนกับ 1 แล้ว
- ผลตอบแทน (a ^ b * c) mod n
p :=ผู้ช่วย(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