Cho năm số nguyên a, b, c, d, n. Tính ((a^b)^(c^d)) mod n.
Ví dụ
Input: a=2, b=3, c=2, d=4, n=10 → Output: 6
2³=8, 2⁴=16, 8¹⁶=281474976710656, 281474976710656 mod 10 = 6
Thuật toán (dựa trên định lý Euler)
Muốn tính a^(b × c^d) mod n. Sử dụng: a^k mod n = a^(k mod φ(n)) mod n (nếu gcd(a,n)=1).
Hàm helper(n) tính φ(n) - hàm Euler totient.
Các trường hợp đặc biệt:
- b=0 hoặc (c=0 và d≠0): mũ = 0 → kết quả 1 mod n
- c=1 hoặc d=0: mũ = b → a^b mod n
- a=0 hoặc a%n=0: kết quả 0
- d=1: mũ = b×c → a^(b×c) mod n
- Trường hợp chung: e = (c^d mod φ(n)) + φ(n), kết quả = (a^b mod n)^e mod n
Mã nguồn
def helper(n):
"""Tính φ(n) - hàm Euler totient"""
p = n
i = 2
while i * i <= n:
if n % i == 0:
p -= p // i
while n % i == 0:
n //= i
i += 2 if i != 2 else 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)) # Output: 6Giải thích chi tiết
Định lý Euler: a^φ(n) ≡ 1 (mod n) nếu gcd(a,n)=1. Do đó a^k ≡ a^(k mod φ(n)) (mod n).
Tuy nhiên khi k < φ(n), công thức không áp dụng trực tiếp. Thêm φ(n) vào mũ (e = c^d mod φ(n) + φ(n)) đảm bảo mũ đủ lớn.
Hàm pow(base, exp, mod) của Python tính lũy thừa modulo hiệu quả O(log exp).