โปรแกรมหาค่าสมการกำลังซ้อนใน Python

กำหนดจำนวนเต็ม 5 ตัว a, b, c, d, n ต้องการหาค่า ((a^b)^(c^d)) mod n หรือ a^(b × c^d) 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

วิธีแก้ปัญหา

1. สร้างฟังก์ชัน helper(n) คำนวณฟังก์ชันออยเลอร์ φ(n) (Euler's totient function)
2. จัดการกรณีพิเศษ: b=0, c=0, d=0, a=0, d=1
3. ใช้ทฤษฎีออยเลอร์: a^φ(n) ≡ 1 (mod n) เมื่อ gcd(a,n)=1
4. คำนวณ e = (c^d) mod φ(n) + φ(n) เพื่อจัดการกรณีเลขยกกำลังใหญ่
5. คำนวณ ((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))

อินพุต / เอาต์พุต

Input:  2, 3, 2, 4, 10
Output: 6

หลักการ: ใช้ทฤษฎีออยเลอร์ (Euler's theorem) และการยกกำลังแบบ modulo (modular exponentiation) เพื่อคำนวณกำลังซ้อนขนาดใหญ่ได้อย่างมีประสิทธิภาพ