Temeller

Modüler aritmetik

Mod, kongrüanslar, tersler, Fermat - hashing ve prefix-mod DP’nin temeli.

Soru: 23 elemanlı bir dizide toplamı 5’e bölünen kaç alt dizi var?

Naif O(n²) 530 çifti dolaşır. Ama mod 5 kalanlarına bakarsan O(n)’e inersin. Bu sayfa, modüler aritmetiğin hash map’lerden prefix-mod DP’ye nerelerde devreye girdiğini açar.

Sayılarla: mod bir saat gibidir

(a + b) mod m, saatin üzerinde ilerler. m = 12 için 10 + 5 = 3 (gece yarısından 5 saat sonra). mod m her zaman 0..m-1 aralığında kalır. Saati döndür ve sonucun nasıl döneceğini izle.

Özellikler (mülakatta hızlı hatırla):

• (a + b) mod m = ((a mod m) + (b mod m)) mod m
• (a · b) mod m = ((a mod m) · (b mod m)) mod m
• a ≡ b (mod m) iff m | (a - b)

Türetme: prefix-mod ile alt dizi sayma

Hedef: toplamı K’ya bölünen alt dizi sayısı. prefix[i] = nums[0] + … + nums[i-1]tanımla. Alt dizi [l, r]’nin toplamı prefix[r+1] - prefix[l]. Bu, K’ya bölünür demek (prefix[r+1] - prefix[l]) mod K == 0, yaniprefix[r+1] ≡ prefix[l] (mod K).

Yani: aynı kalanlara sahip prefix’leri say. count[r] = kalan prefix[r]’den kaç önce. Her kalan için kaç kez görüldüğünü bir hash map’ta tut, toplamı topla → O(n).

Örnek: nums = [4, 5, 0, -2, -3, 1], K = 5. Prefix mod 5’ler:0, 4, 4, 4, 2, 4, 0. Aynı kalan çiftleri: (0,0), (4,4)’ten 3’er, (4,4)’ten daha fazla → toplam 7. LC 974’ün çözümü budur.

Tuzak: “negatif sayılarda mod yanlış çalışır”

Dikkat: -7 mod 5 Python’da 3 verir ama C# / TypeScript’te -7 % 5 = -2. Negatif kalanları pozitife çek: ((x % K) + K) % K. Prefix-mod DP’de bu klasik hata; negatif sayılar içeren dizilerde kalanları yanlış gruplarsın.

Sıradaki adım

• LC 523 Continuous Subarray Sum - prefix-mod, boyut ≥ 2 kısıtı.
• LC 974 Subarray Sums Divisible by K - yukarıdaki örneğin kaynağı.
• LC 560 Subarray Sum Equals K - aynı prefix fikri, mod yerine hash.
• hashing kalıbı - kalan saymak için hash map.

Alıştırma

Saatte a = 8, b = 9, m = 12 ayarla. Sonucu tahmin et (17 mod 12). Şimdi m = 5’e geçir. Bu, mod’ün sadece “bölme kalanı” değil, sayıyı bir halkaya (ring) sarmanın neden işe yaradığını gösterir.

← Tüm matematik konuları →