Bir Asal Modulo Üzerinde Çalışma

Yarışma cevapları çok büyüyebilir ve başka yerlerdeki tüm tamsayı türlerinin sınırlarını aşabilir. Bu nedenle problemlerde sayıları küçük tutmak için sonuç genellikle büyük bir asal sayıya göre modülo olarak istenir. 🔢

En sık göreceğiniz asal sayı 1000000007 değeridir ve genellikle 1e9+7 olarak yazılır. Çakışmalardan kaçınacak kadar büyük, 64 bit'e sığacak kadar da küçüktür.

Modülo operatörü, bölme işleminden sonra kalan değeri verir. Örneğin 17 % 5 işleminin sonucu 2'dir; çünkü 17, 5'e bölündüğünde 2 kalanını verir.

Önce toplayıp modülo işlemini en sonda uygulayabilir veya işlem boyunca uygulayabilirsiniz. Her iki durumda da kalan aynı olur; bu nedenle sayıları küçük tutmak için sık sık küçültün.

Aynı kural çarpma için de geçerlidir: çarpımı asal sayıya göre modülo olarak hesaplayın. Python büyük tamsayıları yerleşik olarak destekler; ancak modülo uygulamak her değeri küçük ve işlemleri hızlı tutar.

Uzun bir döngüde her yinelemede % MOD uygulayın. Bu, sayıların aşırı büyümesini önler ve her işlemi ucuz ve öngörülebilir tutar.

Çıkarma, birçok dilde negatif bir kalan üretebilir. Son modülo işleminden önce MOD değerini ekleyin; böylece sonuç güvenli, negatif olmayan aralığa düşer.

İyi haber: Python'daki % operatörü, pozitif bir modül kullanıldığında zaten negatif olmayan bir sonuç döndürür. Bu nedenle -1 % 7 işleminin sonucu -1 değil 6 olur ve ek bir düzeltme yapmanız gerekmez.

Temel fikir şudur: toplama ve çarpma için (a op b) % m ifadesi (a%m op b%m) % m ifadesine eşittir. Böylece girdileri birleştirmeden önce küçültebilirsiniz.

Toplama, çıkarma ve çarpma modül altında sorunsuz çalışır. Ancak normal bölme çalışmaz; bunun için bu kursta ileride modüler ters kullanmanız gerekecektir.

MOD değerini çözümünüzün başında sabit olarak tanımlayın. Tek bir adlandırılmış değer kullanmak, 1000000007 değerini kodun her yerine dağıtmaktan daha güvenlidir; böylece yazım hatalarının gözden kaçma ihtimali azalır.

Çıkarma işleminin modülosunu almadan önce neden MOD değeri eklenir?

Artık 1e9+7 gibi bir asal modül kullanarak büyük sayımları küçük tutabilirsiniz. Toplama, çıkarma ve çarpma işlemlerinde her adımda modülo uygulayın, negatif değerlere dikkat edin ve bölme işlemini ters alma işlemlerine bırakın. 🎯