Fermat ile Modüler Ters
Bir modül altında güvenle bölme yapın.
Fermat ile Modüler Ters, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Bölme Modül Altında Bozulur
Toplama, çıkarma ve çarpma bir modül altında düzgün çalışır; ancak normal bölme çalışmaz. Sayıyı doğrudan bölüp kalanını alamazsınız. ⚠️
Bölmeyi Çarpma ile Değiştirin
Çözüm modüler ters kullanmaktır: x'e bölmek, x'in tersiyle çarpmaya dönüşür. Yani a / b mod m işlemi, a ile b'nin tersini çarpma işlemine dönüşür.
Ters Nedir
x'in tersi, x ile modül altında çarpıldığında 1 veren sayıdır. Normal aritmetikteki 1/x ifadesinin görevini üstlenir.
# x * inv(x) % m == 1Asal Sayılar Bunu Mümkün Kılar
x ile m aralarında asal olduğunda ters vardır. 1e9+7 gibi bir asal modül kullanmak, sıfır olmayan her x'in bir tersi olmasını garanti eder.
Fermat'ın Küçük Teoremi
Fermat'ın küçük teoremi, p asal bir sayıysa ve x, p'nin katı değilse, x'in p eksi birinci kuvvetinin 1'e denk olduğunu söyler.
# x^(p-1) % p == 1Tersi Türetin
x'in bir çarpanını ayırdığınızda geriye onun tersi kalır. Bu nedenle x'in tersi, x'in p eksi 2. kuvvetine yükseltilip p'ye göre modülo alınarak bulunur.
# inv(x) = x^(p-2) % pHızlı Üs Alma ile Hesaplayın
Bu üs çok büyük olduğundan önceki derste öğrendiğiniz hızlı üs alma yöntemini kullanın. Python'da tek bir pow çağrısı tüm işi sizin için yapar.
inv = pow(x, MOD - 2, MOD)Bölme İşlemi İçin Kullanın
Modül altında a bölü b işlemini hesaplamak için a'yı b'nin tersi ile çarpın. Kalan, gerçek bölümün p'ye göre modülosuna tam olarak eşittir.
ans = a * pow(b, MOD - 2, MOD) % MODSıfırın Tersini Asla Almayın
0'ın tersi yoktur; çünkü sıfırla çarpılan hiçbir sayı 1 vermez. Modül altında sıfıra indirgenen bir değere bölme yapmamaya dikkat edin.
Tek Bir Tersin Maliyeti
Fermat yöntemiyle her ters alma işlemi bir hızlı üs alma işlemine eşittir ve O(log p) zaman alır. Birkaç bölme için bu ucuzdur; ancak milyonlarca kez yapıldığında maliyeti birikir.
Çoklu Tersler İçin İpucu
Çok sayıda ters gerektiğinde, her öğe için bir pow çağrısı yapmak yerine akıllıca tasarlanmış doğrusal bir geçişle bunları önceden hesaplayın. Sırada nCr için buna güveneceksiniz.
Hızlı Kontrol
Asal bir modül altında modüler tersi hangi kuvvet verir?
Özet
Artık asal bir modül altında bölme işlemini, pow ile x'in p eksi 2. kuvvetini alarak bulduğunuz modüler ters ile çarpma şeklinde yapabilirsiniz. Yalnızca sıfırın tersini asla almayın. ✅
Sıkça Sorulan Sorular
“Fermat ile Modüler Ters” dersi ücretsiz mi?
Evet — “Fermat ile Modüler Ters” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Fermat ile Modüler Ters” dersinde ne öğreneceğim?
Bir modül altında güvenle bölme yapın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.
“Fermat ile Modüler Ters” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Bir Asal Modulo Üzerinde Çalışma
- Hızlı Modüler Üs Alma
- Fermat ile Modüler Ters
- Önceden Hesaplanmış Faktöriyellerle nCr