AL07-5. Tez darajaga ko‘tarish

aᵇ mod m ni toping. b 10¹⁸ gacha — b marta ko‘paytirish imkonsiz.

Rekursiv g‘oya: aᵇ = (a^(b/2))², b toq bo‘lsa yana bitta a ga ko‘paytiriladi. Har qadamda b ikki barobar kamayadi. Har ko‘paytmadan keyin % m oling. (pow(a, b, m) shu algoritm — o‘zingiz yozib ko‘ring.)

Kirish ma’lumotlari

Bitta qatorda a, b, m.

Chiqish ma’lumotlari

aᵇ mod m.

Cheklovlar

0 ≤ a ≤ 10¹⁸, 0 ≤ b ≤ 10¹⁸, 1 ≤ m ≤ 2·10⁹