Bekerja Modulo Bilangan Prima
Menjumlahkan, mengalikan, dan tetap berada dalam modulo
Bekerja Modulo Bilangan Prima adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 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.
Mengapa Menggunakan Modulo
Jawaban dalam kompetisi dapat menjadi sangat besar, jauh melampaui tipe bilangan bulat apa pun di tempat lain. Karena itu, soal biasanya meminta hasil modulo bilangan prima besar agar angkanya tetap kecil. 🔢
Mengenal Modulo Terkenal
Bilangan prima yang paling sering Anda temui adalah 1000000007, yang sering ditulis sebagai 1e9+7. Bilangan ini cukup besar untuk menghindari kolisi, tetapi cukup kecil untuk ditampung dalam 64 bit.
MOD = 1000000007Arti Modulo
Operator modulo menghasilkan sisa setelah pembagian. Jadi, 17 % 5 adalah 2 karena 17 menyisakan 2 saat dibagi dengan 5.
print(17 % 5) # 2Penjumlahan Tetap Berada di Dalam Modulo
Anda dapat menjumlahkan terlebih dahulu lalu mengambil modulo di akhir, atau mengambil modulo secara bertahap. Sisanya tetap sama, jadi ambillah modulo sesering mungkin agar angkanya tetap kecil.
total = (a + b) % MODPerkalian Juga Tetap Berada di Dalam Modulo
Aturan yang sama berlaku untuk perkalian: ambil modulo hasil kali terhadap bilangan prima tersebut. Python menangani bilangan bulat besar secara bawaan, tetapi mengambil modulo membuat setiap nilai tetap kecil dan operasi tetap cepat.
prod = (a * b) % MODAmbil Modulo Setelah Setiap Langkah
Dalam perulangan panjang, terapkan % MOD pada setiap iterasi. Ini mencegah angka membesar tanpa batas dan membuat setiap operasi tetap murah serta mudah diprediksi.
ans = (ans * i) % MODPengurangan Dapat Menghasilkan Nilai Negatif
Pengurangan dapat menghasilkan sisa negatif dalam banyak bahasa. Tambahkan MOD kembali sebelum mengambil modulo terakhir agar hasilnya berada dalam rentang aman mulai dari 0.
diff = (a - b + MOD) % MODModulo Python yang Praktis
Kabar baiknya, operator % Python sudah menghasilkan nilai nonnegatif untuk modulus positif. Jadi, -1 % 7 menghasilkan 6, bukan -1, sehingga Anda tidak perlu melakukan perbaikan tambahan.
print(-1 % 7) # 6Modulo Terdistribusi pada Operasi
Gagasan utamanya: (a op b) % m sama dengan (a%m op b%m) % m untuk penjumlahan dan perkalian. Dengan begitu, Anda dapat mengambil modulo masukan sebelum menggabungkannya.
Pembagian Adalah Pengecualiannya
Penjumlahan, pengurangan, dan perkalian bekerja dengan baik menggunakan modulo. Namun, pembagian biasa tidak demikian, dan nanti Anda memerlukan invers modulo untuk melakukannya dalam kursus ini.
Tetapkan MOD Sekali di Bagian Atas
Tetapkan MOD sebagai konstanta di awal solusi Anda. Satu nilai bernama lebih baik daripada menulis 1000000007 berulang kali di dalam kode, tempat kesalahan ketik dapat tersembunyi.
MOD = 10**9 + 7Pemeriksaan Cepat
Mengapa Anda perlu menambahkan MOD sebelum mengambil modulo dari suatu pengurangan?
Ringkasan
Sekarang Anda dapat menjaga jumlah yang sangat besar tetap kecil dengan modulus prima seperti 1e9+7. Ambil modulo setelah setiap penjumlahan, pengurangan, dan perkalian, perhatikan nilai negatif, dan gunakan pembagian hanya untuk invers. 🎯
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Bekerja Modulo Bilangan Prima” gratis?
Ya — teks lengkap “Bekerja Modulo Bilangan Prima” 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 “Bekerja Modulo Bilangan Prima”?
Menjumlahkan, mengalikan, dan tetap berada dalam modulo 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 1 dari 4.
Berapa lama pelajaran “Bekerja Modulo Bilangan Prima” 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
- Bekerja Modulo Bilangan Prima
- Eksponensiasi Modular Cepat
- Invers Modular melalui Fermat
- nCr dengan Faktorial yang Telah Dihitung