Pengeksponenan Modular Pantas
Kira kuasa dengan pow(a, b, m).
Pengeksponenan Modular Pantas ialah pelajaran Competitive Programming Academy percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Competitive Programming Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Masalah Pemangkatan
Anda sering perlu menaikkan nombor kepada eksponen yang sangat besar, semuanya di bawah modulo. Mendarab satu faktor pada satu masa akan mengambil terlalu banyak langkah. ⚡
Kaedah Naif Terlalu Perlahan
Gelung yang mendarab b kali berjalan dalam O(b) langkah. Dengan eksponen yang hampir satu bilion, proses itu melebihi had masa sebelum sempat selesai.
for _ in range(b): r = r * a % MODKuasakan Dua untuk Lebih Pantas
Petuanya ialah mengkuasakan dua: a berpangkat 8 sama dengan ((a dikuasakan dua) dikuasakan dua) dikuasakan dua. Setiap pengkuasaan dua menggandakan eksponen, jadi Anda boleh mencapai kuasa besar dalam beberapa langkah sahaja.
Baca Eksponen dalam Perduaan
Setiap eksponen ialah jumlah kuasa dua, iaitu bentuk perduaannya. Jadi, Anda hanya mendarab kuasa asas yang bitnya bernilai 1 dan melangkau yang lain.
# 13 = 1101 -> a^8 * a^4 * a^1Periksa Bit Terendah
Lihat b & 1 untuk menguji bit terendah. Jika nilainya 1, gabungkan asas semasa ke dalam hasil yang sedang dikira sebelum meneruskan.
if b & 1: result = result * base % MODAnjak dan Kuasakan Dua Setiap Pusingan
Selepas setiap bit, kuasakan dua asas dan anjak eksponen ke kanan sebanyak satu kedudukan. Gelung ini hanya berjalan kira-kira 30 hingga 60 kali untuk sebarang input yang munasabah.
base = base * base % MOD
b >>= 1Satukan Semuanya
Mulakan result dengan 1, kemudian ulangi gelung selagi eksponen positif. Idea pemangkatan pantas ini juga dipanggil perduaan atau pemangkatan melalui pengkuasaan dua.
result = 1
while b > 0:
if b & 1: result = result*base%MOD
base = base*base%MOD
b >>= 1Berjalan dalam Masa Logaritma
Oleh sebab setiap pusingan membahagi dua eksponen, kosnya ialah O(log b). Ini menukar satu bilion pendaraban kepada kira-kira tiga puluh, dan masih jauh dalam mana-mana had.
Python Menyediakan pow
Anda jarang perlu menulis gelung itu sendiri: pow(a, b, m) terbina dalam Python melakukan pemangkatan modulo pantas pada kelajuan C natif.
print(pow(2, 100, MOD))Mengapa Ini Penting Tidak Lama Lagi
Kuasa pantas ialah enjin di sebalik invers modulo menggunakan Fermat, yang akan Anda pelajari seterusnya. Kuasainya sekarang dan pembahagian di bawah modulo menjadi mudah.
Perhatikan Asas Dahulu
Kurangkan asas menggunakan base % MOD sebelum gelung. Asas yang sudah lebih besar daripada modulo akan membesarkan setiap langkah pengkuasaan dua.
base = a % MODSemakan Pantas
Seberapa pantaskah pemangkatan modulo pantas?
Rumusan
Sekarang Anda boleh menaikkan nombor kepada eksponen yang sangat besar dalam O(log b) dengan mengkuasakan dua dan membaca bit. Dalam Python, hanya panggil pow(a, b, m) dan teruskan. 🚀
Pelajari Python dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “Pengeksponenan Modular Pantas” percuma?
Ya — teks penuh “Pengeksponenan Modular Pantas” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Competitive Programming Academy, tingkat taraf kepada CoddyKit PRO. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Pengeksponenan Modular Pantas”?
Kira kuasa dengan pow(a, b, m). Anda berlatih Competitive Programming Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Competitive Programming Academy?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Competitive Programming Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.
Berapa lamakah pelajaran “Pengeksponenan Modular Pantas” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Bekerja Modulo Perdana
- Pengeksponenan Modular Pantas
- Invers Modular melalui Fermat
- nCr dengan Faktorial Pra-kiraan