Lanjut50 XPUnit 9: Fungsi dan Rekursi, soal 2 dari 9
Pangkat Cepat
Hitung A pangkat B modulo M untuk B yang sangat besar.
Mengalikan A sebanyak satu triliun kali jelas terlalu lama. Triknya: A pangkat 10 sama dengan (A pangkat 5) kuadrat, dan A pangkat 5 sama dengan A dikali (A pangkat 2) kuadrat. Setiap langkah, pangkatnya terbelah dua.
Masukan
Satu baris berisi A (0 sampai 10^9), B (0 sampai 10^15), dan M (1 sampai 1000000).
Keluaran
Nilai A pangkat B dibagi M, ambil sisanya. Anggap 0 pangkat 0 bernilai 1.
Contoh masukan dan keluaran
Contoh 1
Masukan
2 10 1000
Keluaran
24
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Bila B genap, A^B = (A^(B/2))². Bila ganjil, A^B = A × A^(B-1). Kasus dasarnya A^0 = 1.
Petunjuk 2
Ambil sisa bagi M di setiap langkah supaya angkanya tidak membengkak. Hitung setengahnya sekali saja, lalu kuadratkan.