Mình xin chia sẻ lời giải bài này như sau:

• Đặt \(p = 10^{18}+9\)
• Đầu tiên, ta có nhận xét rằng: \(p\) là một số nguyên tố, do đó: \(\phi(p)=p-1\)

Theo định lý Fermat bé, ta có: \(a^{\phi(p)}\equiv 1(\text{ mod }p)\)

Tiếp theo, ta sẽ đi tìm dư của \(b^{c}\) cho \(\phi(p)\).

Để thực hiện phép tính này, ta sử dụng luỹ thừa nhị phân

và giả sử rằng: \(b^{c}\equiv d(\text{ mod }\phi(p))\)

Hay \(b^c = q*\phi(p) + d\) với \(q\in \mathbb{N}\)

Lúc này: \(a^{b^c}=a^{q*\phi(p) + d} = (a^{\phi(p)})^q * a^{d}\equiv a^{d}(\text{ mod }p)\)

Công việc còn lại chỉ là, ta tiếp tục áp dụng luỹ thừa nhị phân để tính \(a^{d}\text{%}p\) là xong

Ps: Nếu các bạn đã cố gắng hết sức, nhưng vẫn chưa ac, có thể tham khảo code tại đây