Bài 9.4. Thách Thức Cửa Ải Số Học - [Độ khó: Khá]

Trong một ngôi đền cổ xưa, có một cánh cửa bí ẩn chỉ mở ra khi bạn nhập đúng một "mật mã số học". Mật mã này được tính bằng công thức (A^B) % M, trong đó A là số cơ sở, B là số mũ, và M là modulo. Vấn đề là A, B và M có thể là những số rất lớn, khiến việc tính toán trực tiếp trở nên bất khả thi. Bạn cần viết một chương trình để tính toán mật mã này một cách hiệu quả.

INPUT FORMAT

Một dòng duy nhất chứa ba số nguyên A, B, và M (1 <= A, M <= 10^9, 0 <= B <= 10^18).

OUTPUT FORMAT

In ra một số nguyên duy nhất là kết quả của (A^B) % M.

Ví dụ:

Input:

2 10 100

Output:

24

Giải thích:

• A = 2, B = 10, M = 100.
• Ta cần tính (2^10) % 100.
• 2^10 = 1024.
• 1024 % 100 = 24. (Gợi ý: Sử dụng thuật toán lũy thừa theo modulo (Binary Exponentiation hay Exponentiation by Squaring) để xử lý B lớn một cách hiệu quả.)