Invers Modular melalui Fermat
Melakukan pembagian secara aman di bawah modulus
Invers Modular melalui Fermat adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 3 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 Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Pembagian Gagal dengan Modulo
Penjumlahan, pengurangan, dan perkalian bekerja dengan baik menggunakan modulus, tetapi pembagian biasa tidak. Anda tidak dapat begitu saja membagi lalu mengambil sisanya. ⚠️
Ganti Pembagian dengan Perkalian
Solusinya adalah invers modulo: pembagian dengan x diubah menjadi perkalian dengan invers x. Jadi, a / b modulo m berubah menjadi a dikalikan invers b.
Arti Invers
Invers dari x adalah bilangan yang menghasilkan 1 ketika dikalikan dengan x menggunakan modulus. Invers berperan seperti 1/x dalam aritmetika biasa.
# x * inv(x) % m == 1Bilangan Prima Membuatnya Mungkin
Invers hanya ada jika x tidak memiliki faktor persekutuan dengan m. Menggunakan modulus prima seperti 1e9+7 menjamin setiap x yang bukan nol memiliki invers.
Mengenal Teorema Kecil Fermat
Teorema kecil Fermat menyatakan bahwa untuk bilangan prima p, x pangkat p dikurangi 1 kongruen dengan 1, selama x bukan kelipatan p.
# x^(p-1) % p == 1Menurunkan Rumus Invers
Pisahkan satu faktor x, dan bagian sisanya pasti merupakan inversnya. Jadi, invers x adalah x yang dipangkatkan dengan p dikurangi 2, lalu diambil modulo p.
# inv(x) = x^(p-2) % pHitung dengan Perpangkatan Cepat
Eksponen tersebut sangat besar, jadi gunakan perpangkatan cepat dari pelajaran sebelumnya. Di Python, satu pemanggilan pow melakukan semuanya untuk Anda.
inv = pow(x, MOD - 2, MOD)Gunakan untuk Membagi
Untuk menghitung a dibagi b menggunakan modulo, kalikan a dengan invers b. Sisanya tepat sama dengan hasil bagi sebenarnya modulo p.
ans = a * pow(b, MOD - 2, MOD) % MODJangan Pernah Mencari Invers Nol
Tidak ada invers dari 0 karena tidak ada bilangan yang jika dikalikan dengan nol menghasilkan satu. Pastikan Anda tidak membagi dengan nilai yang menjadi nol setelah menggunakan modulus.
Biaya Satu Invers
Setiap invers Fermat adalah satu perpangkatan cepat, sehingga membutuhkan waktu O(log p). Ini murah untuk beberapa pembagian, tetapi dapat menjadi besar jika dilakukan jutaan kali.
Petunjuk tentang Invers secara Berkelompok
Saat Anda memerlukan banyak invers, lakukan praperhitungan dengan satu lintasan linear yang cerdas, bukan dengan satu pow untuk setiap elemen. Anda akan mengandalkan teknik ini untuk nCr berikutnya.
Pemeriksaan Cepat
Pangkat berapa yang menghasilkan invers modulo untuk bilangan prima?
Ringkasan
Sekarang Anda dapat melakukan pembagian menggunakan modulus prima dengan mengalikan invers modulo, yang diperoleh sebagai x pangkat p dikurangi 2 melalui pow. Ingat, jangan pernah mencari invers dari nol. ✅
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Invers Modular melalui Fermat” gratis?
Ya — teks lengkap “Invers Modular melalui Fermat” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Invers Modular melalui Fermat”?
Melakukan pembagian secara aman di bawah modulus Kamu berlatih Competitive Programming Academy 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 Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy 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 3 dari 4.
Berapa lama pelajaran “Invers Modular melalui Fermat” 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 Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy 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
- Bekerja Modulo Bilangan Prima
- Eksponensiasi Modular Cepat
- Invers Modular melalui Fermat
- nCr dengan Faktorial yang Telah Dihitung