14. Modulo dan teorema-teoremanya

Operasi % sudah dipakai sejak Bab 03 untuk memeriksa ganjil-genap. Bab ini membahasnya sebagai alat matematika: sifat-sifatnya, cara memakainya pada bilangan raksasa, dan dua teorema yang sering muncul di soal OSN.

Sisa bagi

a % m adalah sisa ketika a dibagi m. Untuk a dan m positif, hasilnya selalu di antara 0 dan m − 1.

cout << 17 % 5 << "\n";     // 2
cout << 20 % 5 << "\n";     // 0
cout << 3 % 5 << "\n";      // 3

Dua bilangan disebut kongruen modulo m kalau sisanya sama:

17 ≡ 2 (mod 5), karena keduanya bersisa 2.

Cara membacanya: modulo membagi semua bilangan bulat menjadi m kelompok. Dalam modulo 5, bilangan 2, 7, 12, 17, dan 22 berada di kelompok yang sama.

Gambaran yang paling membantu adalah jam. Jam dinding bekerja modulo 12: pukul 10 ditambah 5 jam menjadi pukul 3, bukan pukul 15, karena 15 mod 12 = 3. Semua sifat modulo di bawah ini sebenarnya sifat yang sudah kamu pakai sejak kecil saat membaca jam:

int mod_benar(int a, int m) {
    return ((a % m) + m) % m;
}

Sifat-sifat modulo

Inilah alasan modulo begitu berguna: ia "tembus" terhadap penjumlahan, pengurangan, dan perkalian.

Alasannya mudah dilihat untuk penjumlahan. Tulis a = q·m + r₁ dan b = p·m + r₂. Maka:

a + b = (q + p)·m + (r₁ + r₂)

Bagian (q + p)·m habis dibagi m, jadi tidak menyumbang apa pun ke sisanya. Yang tersisa hanya r₁ + r₂, yaitu jumlah kedua sisa. Hal yang sama berlaku untuk perkalian, karena semua suku hasil kali kecuali r₁ · r₂ mengandung faktor m.

Artinya: kamu boleh mengambil sisa kapan saja di tengah perhitungan, tanpa mengubah jawaban akhir. Inilah yang membuat program bisa menjawab soal seperti "berapa 2¹⁰⁰⁰ mod 1.000.000.007" tanpa pernah menyimpan bilangan seribu digit.

Kenapa 1.000.000.007

Soal sering meminta jawaban "modulo 10⁹ + 7". Alasannya:

• Jawaban sebenarnya terlalu besar untuk disimpan (bisa ribuan digit).
• 10⁹ + 7 adalah bilangan prima, yang membuat pembagian modulo bisa dikerjakan dengan teorema Fermat.
• Hasil kali dua bilangan di bawah 10⁹ + 7 masih muat di long long (sekitar 10¹⁸ < 9,2 × 10¹⁸).

Pola penulisannya:

const long long MOD = 1000000007;

long long hasil = 1;
for (int i = 1; i <= n; i++) {
    hasil = hasil * i % MOD;        // ambil sisa setiap kali
}

Telusuri untuk n = 5 dengan MOD = 7, supaya angkanya kecil dan mudah diperiksa:

Periksa: 5! = 120, dan 120 = 17 × 7 + 1, jadi 120 mod 7 memang 1. Perhatikan bahwa nilai antaranya tidak pernah melebihi 24 walaupun jawaban sesungguhnya 120 — dan pada soal sungguhan, itulah bedanya antara bilangan yang muat di long long dan bilangan sejuta digit.

Pangkat modulo cepat

Menghitung aᵇ mod m dengan perulangan b kali memerlukan O(b) langkah — mustahil untuk b = 10¹⁸. Caranya dipercepat dengan membelah pangkat:

• kalau b genap: aᵇ = (aᵇ⁄²)²
• kalau b ganjil: aᵇ = a × aᵇ⁻¹

Setiap langkah membagi b dua, jadi jumlah langkahnya O(log b). Untuk b = 10¹⁸ itu sekitar 60 langkah.

Cara kerjanya bisa dibaca dari bentuk biner pangkatnya. Karena 5 = 101 dalam biner, artinya 5 = 4 + 1, sehingga:

a⁵ = a⁴ · a¹

Perulangan di bawah ini memeriksa bit b satu per satu dari kanan. Variabel a dikuadratkan terus sehingga berturut-turut bernilai a¹, a², a⁴, a⁸, …, dan hanya dikalikan ke hasil saat bit yang bersangkutan menyala.

long long pangkat_mod(long long a, long long b, long long m) {
    long long hasil = 1;
    a %= m;
    while (b > 0) {
        if (b % 2 == 1) hasil = hasil * a % m;
        a = a * a % m;
        b /= 2;
    }
    return hasil;
}

Telusuri pangkat_mod(3, 5, 1000):

Benar: 3⁵ = 243.

Bacanya bersama bentuk biner tadi: bit yang menyala pada 5 = 101₂ adalah bit ke-0 dan bit ke-2, sehingga yang dikalikan ke hasil adalah a¹ = 3 dan a⁴ = 81. Hasilnya 3 × 81 = 243.

Teorema Fermat kecil

Kalau p bilangan prima dan a tidak habis dibagi p, maka aᵖ⁻¹ ≡ 1 (mod p).

Contoh: p = 7, a = 3 → 3⁶ = 729 = 104 × 7 + 1, jadi 729 ≡ 1 (mod 7).

Gunanya di OSN ada dua.

1. Memendekkan pangkat raksasa. Karena aᵖ⁻¹ ≡ 1, pangkat bisa diambil modulo p − 1:

a^b mod p = a^(b mod (p−1)) mod p, asalkan a tidak habis dibagi p.

2. Pembagian modulo. Kalikan kedua sisi dengan a⁻¹:

a⁻¹ ≡ aᵖ⁻² (mod p)

Jadi membagi dengan a dalam dunia modulo p sama dengan mengalikan dengan pangkat_mod(a, p - 2, p).

long long invers(long long a, long long p) {
    return pangkat_mod(a, p - 2, p);        // hanya kalau p prima
}

// (x / y) mod p
long long bagi_mod(long long x, long long y, long long p) {
    return x % p * invers(y, p) % p;
}

Ini yang membuat rumus kombinasi (Bab 17) bisa dihitung modulo 10⁹ + 7, walaupun rumusnya berisi pembagian faktorial.

Pola soal yang memakai modulo

Digit terakhir. Digit satuan suatu bilangan adalah nilainya mod 10. Digit terakhir 7¹⁰⁰ adalah pangkat_mod(7, 100, 10).

Siklus dan jam. Hari ke-n dari hari Senin adalah n % 7. Jarum jam setelah n jam adalah (sekarang + n) % 12.

Uji habis dibagi. Sebuah bilangan habis dibagi 3 (atau 9) kalau jumlah digitnya habis dibagi 3 (atau 9). Alasannya: 10 ≡ 1 (mod 9), jadi setiap digit menyumbang nilainya sendiri.

Menghindari luapan. Soal yang jawabannya besar hampir selalu meminta hasilnya modulo suatu bilangan, justru supaya bisa dihitung.

Pekerjaan rumah

Kesalahan yang paling sering

Tips OSN

Kalimat "keluarkan jawabannya modulo 1.000.000.007" berarti jawabannya sangat besar. Kalimat itu sekaligus petunjuk bahwa yang diminta adalah menghitung, bukan menyusun: soal yang jawabannya perlu disisakan hampir selalu soal kombinatorika atau DP dengan jumlah cara yang meledak.

Ambil sisa di setiap langkah, bukan di akhir. Menunda % MOD sampai baris terakhir membuat penampungnya meluap jauh sebelum sampai ke sana. Aturan praktisnya: setiap kali ada + atau * pada nilai yang sudah bermodulo, langsung ikuti dengan % MOD.

Perkalian dua sisa memerlukan long long. Dua bilangan di bawah 10⁹ + 7 yang dikalikan mencapai sekitar 10¹⁸ — melewati int lebih dari empat ratus juta kali lipat, dan masih muat di long long. Inilah alasan modulusnya dipilih sebesar itu tetapi tidak lebih.

% di C++ bisa memberi hasil negatif. -7 % 3 bernilai -1, bukan 2. Kalau ada pengurangan atau data negatif, bungkus dengan pola baku:

hasil = ((a - b) % MOD + MOD) % MOD;

Kesalahan ini tidak terlihat pada contoh soal yang seluruhnya positif, dan baru muncul sebagai Wrong Answer pada berkas uji.

Pembagian tidak ada di dunia modulo. (a / b) % MOD hampir selalu salah. Yang benar adalah mengalikan dengan invers modulo, dan untuk modulus prima inversnya dihitung dengan pangkat(b, MOD - 2). Setiap kali muncul pembagian pada rumus — misalnya pada rumus kombinasi — pikirkan invers.

Eksponen yang terlalu besar disisakan terhadap MOD − 1. Teorema Fermat kecil memberi a^(p−1) ≡ 1 (mod p) untuk p prima dan a bukan kelipatan p. Perhatikan modulus yang berbeda: alasnya bermodulo p, eksponennya bermodulo p − 1. Tertukar adalah kesalahan yang sangat sering terjadi.

Ringkasan

• a % m adalah sisa bagi; untuk a dan m positif hasilnya 0 sampai m − 1. Untuk a negatif, C++ memberi hasil negatif — perbaiki dengan ((a % m) + m) % m.
• Modulo "tembus" terhadap penjumlahan, pengurangan, dan perkalian, jadi sisa boleh diambil kapan saja di tengah perhitungan.
• Modulo tidak tembus terhadap pembagian; pembagian dikerjakan dengan invers modulo.
• 10⁹ + 7 dipilih karena prima dan karena hasil kali dua bilangan di bawahnya masih muat di long long.
• Pangkat modulo cepat memerlukan O(log b) langkah dengan membelah pangkat menjadi bentuk binernya.
• Teorema Fermat kecil: untuk p prima dan a tidak habis dibagi p, aᵖ⁻¹ ≡ 1 (mod p). Akibatnya invers a adalah pangkat_mod(a, p - 2, p).

Latihan bergaya OSN

Ketiga soal berikut memakai tiga alat berbeda dari bab ini: pangkat modulo cepat, teorema Fermat kecil, dan sifat sisa pada jumlah awalan.

Kerangka ketiganya ada di exercises/14/osn/.

Soal 1 — Sisa Deret Pangkat

Hitung 1^K + 2^K + … + N^K, lalu keluarkan sisanya jika dibagi 1.000.000.007.

Format masukan. Satu baris berisi dua bilangan bulat N dan K.

Format keluaran. Satu baris berisi sisa hasil penjumlahan itu.

Batasan.

• 1 ≤ N ≤ 10⁶
• 1 ≤ K ≤ 10⁹

Contoh masukan

3 2

Contoh keluaran

14

Penjelasan. 1² + 2² + 3² = 1 + 4 + 9 = 14, dan 14 lebih kecil daripada modulusnya sehingga sisanya tetap 14. Perhatikan besarnya K: menghitung i^K dengan mengalikan K kali jelas tidak mungkin.

Kerangkanya: exercises/14/osn/01-deret-pangkat.cpp

Soal 2 — Pangkat Bertingkat

Hitung A pangkat (B pangkat C), lalu keluarkan sisanya jika dibagi 1.000.000.007.

Format masukan. Satu baris berisi tiga bilangan bulat A, B, dan C.

Format keluaran. Satu baris berisi sisanya.

Batasan. 1 ≤ A, B, C ≤ 10⁹. Perhatikan bahwa A selalu lebih kecil daripada 1.000.000.007, jadi A tidak pernah merupakan kelipatan modulusnya.

Contoh masukan

2 3 2

Contoh keluaran

512

Penjelasan. B^C = 3² = 9, dan 2⁹ = 512. Untuk masukan yang lebih besar, B^C sendiri tidak bisa disimpan di tipe apa pun — misalnya 10⁹ pangkat 10⁹ punya sekitar sembilan miliar digit. Jadi eksponennya harus diperkecil lebih dulu, dan syarat pada A di atas adalah yang membuatnya sah.

Kerangkanya: exercises/14/osn/02-pangkat-bertingkat.cpp

Soal 3 — Potongan Habis Dibagi K

Diberikan barisan N bilangan bulat. Hitung ada berapa potongan berurutan yang tidak kosong dan jumlah isinya habis dibagi K.

Format masukan. Baris pertama berisi dua bilangan bulat N dan K. Baris kedua berisi N bilangan bulat.

Format keluaran. Satu baris berisi banyaknya potongan.

Batasan.

• 1 ≤ N ≤ 200.000
• 1 ≤ K ≤ 10⁶
• −10⁹ ≤ Aᵢ ≤ 10⁹

Contoh masukan

5 3
1 2 3 4 1

Contoh keluaran

4

Penjelasan. Potongannya adalah 2 3 4 (jumlah 9), 3 (jumlah 3), 1 2 3 (jumlah 6), dan 1 2 (jumlah 3). Bilangan negatif juga mungkin muncul pada berkas uji, dan % di C++ memberi sisa negatif untuk bilangan negatif — itu bagian dari soalnya.

Kerangkanya: exercises/14/osn/03-subarray-habis-dibagi.cpp

Bingung atau sudah selesai? Buka halaman pembahasan PR.