Chương trình tính giá trị lũy thừa 2^(2^p) mod q trong Python

Cho hai số nguyên p và q. Tính 2^(2^p) mod q.

Ví dụ

Input: p=5, q=6 → Output: 4

2^(2^5) = 2^32 = 4294967296. 4294967296 mod 6 = 4.

Giải pháp tối ưu

Sử dụng hàm pow(base, exp, mod) tích hợp của Python hỗ trợ modulo lũy thừa lớn:

def solve(p, q):
    res = pow(2, 2 ** p, q)
    return res

print(solve(5, 6))  # Output: 4

Giải thích

• pow(2, 2**p, q) tính (2^(2^p)) % q hiệu quả mà không cần tạo số khổng lồ 2^(2^p)
• Python dùng thuật toán bình phương lặp (exponentiation by squaring) với độ phức tạp O(log exponent)
• Độ phức tạp: O(p) do 2**p tạo số có ~2^p bit, nhưng pow xử lý modulo trong quá trình tính

Lưu ý: Với p rất lớn (ví dụ p=10^6), 2**p sẽ gây lỗi bộ nhớ. Cách khắc phục: dùng tính chất modulo lũy thừa lồng nhau (Euler totient) như bài 1003095677.