LBC_2F - Mũ cực mạnh

https://luyencode.net/problem/lbc_2f

Định lý Fermat nhỏ:

$a^{m-1}\equiv 1(\mathrm{mod}m)$ nếu

$m$ là số nguyên tố và

$gcd(a,m)=1$

Suy ra

$a^x\equiv a^{x\mathrm{\%}(m-1)}(\mathrm{mod}m)$

Ví dụ, cần tính

$a^{100}\mathrm{mod}19$

$a^{100}\equiv a^{18}\cdot a^{18}\cdot a^{18}\cdot a^{18}\cdot a^{18}\cdot a^{10}(\mathrm{mod}m)$

$a^{100}\equiv 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot a^{10}(\mathrm{mod}m)$

$a^{100}\equiv a^{10}(\mathrm{mod}m)$

Vậy thay vì tính

$a^{b^c}$, ta sẽ tính

$x=b^c$

$\mathrm{\%}$

$(m-1)$, rồi sau đó tính

$a^x$

$\mathrm{\%}$

$m$.

Chú ý là truy vấn cần in ra các tổng của

$a^{b^c}$ theo thứ tự xoay vòng, ta có thể dùng một mảng tổng dồn để tính trước.