0Pricing
Coding Interview Prep · Pelajaran

Eksponensiasi Modular Cepat

Menghitung pangkat dengan pow(a, b, m)

Eksponensiasi Modular Cepat adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Masalah Perpangkatan

Anda sering perlu menghitung suatu bilangan berpangkat sangat besar, semuanya dalam suatu modulus. Mengalikan satu faktor setiap kali akan membutuhkan terlalu banyak langkah. ⚡

Cara Naif Terlalu Lambat

Perulangan yang mengalikan b kali berjalan dalam O(b) langkah. Jika eksponennya mendekati satu miliar, proses ini akan melewati batas waktu sebelum selesai.

for _ in range(b): r = r * a % MOD

Kuadratkan untuk Mencapai Pangkat Lebih Cepat

Triknya adalah mengkuadratkan: a pangkat 8 sama dengan ((a kuadrat) kuadrat) kuadrat. Setiap pengkuadratan menggandakan eksponen, sehingga Anda dapat mencapai pangkat besar dalam sedikit langkah.

Baca Eksponen dalam Biner

Setiap eksponen merupakan penjumlahan pangkat dua, yaitu bentuk binernya. Jadi, Anda hanya mengalikan pangkat dasar yang bitnya bernilai 1 dan melewati sisanya.

# 13 = 1101 -> a^8 * a^4 * a^1

Periksa Bit Terendah

Lihat b & 1 untuk menguji bit terendah. Jika nilainya 1, kalikan basis saat ini ke hasil yang sedang dihitung sebelum melanjutkan.

if b & 1: result = result * base % MOD

Geser dan Kuadratkan di Setiap Putaran

Setelah setiap bit, kuadratkan basis dan geser eksponen ke kanan satu posisi. Perulangan ini hanya berjalan sekitar 30 hingga 60 kali untuk masukan realistis apa pun.

base = base * base % MOD
b >>= 1

Menggabungkan Semuanya

Mulai hasil dari 1, lalu lakukan perulangan selama eksponen masih positif. Gagasan perpangkatan cepat ini juga disebut perpangkatan biner atau perpangkatan dengan pengkuadratan.

result = 1
while b > 0:
    if b & 1: result = result*base%MOD
    base = base*base%MOD
    b >>= 1

Berjalan dalam Waktu Logaritmik

Karena setiap putaran membagi dua eksponen, biayanya adalah O(log b). Dengan begitu, satu miliar perkalian berubah menjadi sekitar tiga puluh perkalian, jauh di bawah batas waktu apa pun.

Python Menyediakan pow

Anda hampir tidak pernah perlu menulis perulangannya sendiri: fungsi bawaan Python, pow(a, b, m), melakukan perpangkatan modulo cepat dengan kecepatan kode C murni.

print(pow(2, 100, MOD))

Mengapa Ini Segera Penting

Perpangkatan cepat menjadi dasar invers modulo menurut Fermat, yang akan Anda pelajari berikutnya. Kuasai ini sekarang agar pembagian dengan modulo menjadi mudah.

Perhatikan Basis Terlebih Dahulu

Ambil modulo basis dengan base % MOD sebelum perulangan. Jika basis sudah lebih besar daripada modulus, setiap langkah pengkuadratan akan menjadi lebih berat.

base = a % MOD

Pemeriksaan Cepat

Seberapa cepat perpangkatan modulo cepat?

Ringkasan

Sekarang Anda dapat menghitung bilangan berpangkat sangat besar dalam O(log b) dengan mengkuadratkan dan membaca bit. Di Python, cukup panggil pow(a, b, m) lalu lanjutkan. 🚀

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Eksponensiasi Modular Cepat” gratis?

Ya — teks lengkap “Eksponensiasi Modular Cepat” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Eksponensiasi Modular Cepat”?

Menghitung pangkat dengan pow(a, b, m) Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.

Berapa lama pelajaran “Eksponensiasi Modular Cepat” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Bekerja Modulo Bilangan Prima
  2. Eksponensiasi Modular Cepat
  3. Invers Modular melalui Fermat
  4. nCr dengan Faktorial yang Telah Dihitung
← Kembali ke Coding Interview Prep