14. Modulo dan teorema-teoremanya — Pembahasan PR

Berkas .cpp jawabannya ada di exercises/14/homework/solutions/.

Halaman ini dibuka sesudah mencoba sendiri. Bandingkan jalan pikiranmu dengan bagian Cara berpikir, bukan kodenya baris per baris: dua kode yang berbeda bentuk bisa sama-sama benar, dan yang perlu ditiru adalah cara sampai ke sana. Bagian Uji di tiap soal berisi masukan dan keluaran yang sudah diperiksa — jalankan jawabanmu sendiri dengan masukan itu sebelum merasa selesai.

Menjalankan salah satu jawabannya:

g++ -std=c++17 -O2 -o jawab exercises/14/homework/solutions/01-mod-benar.cpp
./jawab

Soal 1 — Modulo yang benar

Soal. Sisa bagi yang selalu di antara 0 dan m − 1, termasuk untuk a negatif.

Cara berpikir. a % m di C++ bisa negatif. Menambahkan m sekali sudah cukup untuk membuatnya positif, karena a % m tidak pernah lebih kecil dari −(m − 1). Sisa % m terakhir mengembalikannya ke rentang bila penambahannya membuat nilainya mencapai m.

Pembahasan.

cout << ((a % m) + m) % m << "\n";

Uji.

Baris ketiga adalah bentuk yang akan sering kamu temui: hasil pengurangan modulo yang jatuh menjadi -1 harus dikembalikan menjadi MOD - 1, bukan dibiarkan negatif.

Kesalahan umum.

• Menulis if (a < 0) a = -a;. Itu mengubah soalnya: −7 mod 3 bukan 7 mod 3.
• Menambahkan m tanpa % m terakhir, sehingga a = 0 memberi jawaban m, bukan 0.

Soal 2 — Faktorial modulo

Soal. n! mod 10⁹ + 7 untuk n sampai sejuta.

Cara berpikir. 1.000.000! punya lebih dari lima juta digit — mustahil disimpan. Sifat perkalian modulo menyelamatkannya: ambil sisa di setiap langkah perkalian, bukan di akhir.

Pembahasan.

long long hasil = 1;
for (int i = 2; i <= n; i++) hasil = hasil * i % MOD;
cout << hasil << "\n";

Untuk n = 10 hasilnya 3.628.800 (masih di bawah MOD, jadi terlihat utuh); untuk n = 1.000.000 hasilnya 641.102.369.

Uji.

Baris ketiga adalah pemeriksaan yang bagus: 20! masih muat di long long, jadi kamu bisa menghitungnya tanpa modulo lalu mengambil sisanya sendiri untuk membandingkan. Mulai 21! cara itu tidak bisa dipakai lagi.

Kesalahan umum.

• Menyimpan hasil sebagai int. hasil * i langsung meluap.
• Mengambil modulo hanya sekali di akhir. Nilai di tengah sudah rusak jauh sebelum itu.
• Memakai double untuk menampung faktorial besar. double kehilangan ketepatan setelah sekitar 15 digit.

Soal 3 — Pangkat modulo cepat

Soal. aᵇ mod m dengan b sampai 10¹⁸.

Cara berpikir. Kunci pemercepatnya: setiap langkah membagi b dua, sambil mengkuadratkan a. Kalau bit terendah b menyala, a sekarang ikut dikalikan ke hasil.

Baris a %= m; di awal penting untuk a yang lebih besar dari m.

Pembahasan.

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;
}

Periksa: 2 10 1000 memberi 24 (2¹⁰ = 1024), dan 3 0 7 memberi 1 — pangkat nol selalu 1.

Uji.

Baris ketiga adalah alasan seluruh fungsi ini ada: pangkatnya 10¹⁸, dan jawabannya tetap muncul seketika karena hanya sekitar 60 kali pengkuadratan yang dikerjakan.

Kesalahan umum.

• Memakai perulangan b kali. Untuk b = 10¹⁸ programnya tidak akan pernah selesai.
• Menulis int untuk a atau hasil. a * a dengan a mendekati 10⁹ membutuhkan long long.
• Lupa bahwa untuk m = 1 jawabannya selalu 0; rumus di atas sudah menanganinya karena hasil * a % 1 selalu 0.

Soal 4 — Uji habis dibagi 9

Soal. Bilangan sampai 100.000 digit, habis dibagi 9 atau tidak.

Cara berpikir. Bilangannya tidak muat di tipe apa pun, jadi dibaca sebagai string. Sifat yang dipakai: 10 ≡ 1 (mod 9), sehingga 10ᵏ ≡ 1 untuk semua k. Artinya setiap digit menyumbang nilainya sendiri, dan bilangan itu kongruen dengan jumlah digitnya modulo 9.

Karakter digit diubah menjadi angka dengan s[i] - '0'.

Pembahasan.

string s;
cin >> s;

long long jumlah = 0;
for (int i = 0; i < (int)s.size(); i++) jumlah += s[i] - '0';

if (jumlah % 9 == 0) cout << "YA\n";
else cout << "TIDAK\n";

Uji.

Baris ketiga adalah inti soalnya: bilangan 24 digit itu tidak muat di long long sama sekali, tetapi jumlah digitnya bisa dihitung selama bilangannya dibaca sebagai string. Ini pola umum untuk soal "bilangan sangat panjang".

Kesalahan umum.

• Mencoba long long n; cin >> n; untuk bilangan 100.000 digit.
• Menjumlahkan s[i] tanpa - '0', sehingga yang dijumlahkan kode karakternya (48 sampai 57).
• Memakai aturan ini untuk pembagi selain 3 dan 9. Untuk 11 aturannya berbeda (jumlah digit berselang-seling), karena 10 ≡ −1 (mod 11).

Tantangan — Invers modulo

Soal. (x / y) mod p dengan p prima.

Cara berpikir. Pembagian tidak punya sifat modulo. Yang dipakai adalah invers: bilangan y⁻¹ yang memenuhi y × y⁻¹ ≡ 1 (mod p). Teorema Fermat kecil memberikannya langsung: y⁻¹ ≡ yᵖ⁻² (mod p).

Setelah invers didapat, pembagian menjadi perkalian:

(x / y) mod p = x × y^(p−2) mod p

Pemeriksaan di akhir adalah kebiasaan bagus: kalikan kembali hasilnya dengan y; kalau benar, hasilnya kembali menjadi x mod p.

Pembahasan.

long long invers(long long a, long long p) {
    return pangkat_mod(a, p - 2, p);
}

long long hasil = x % p * invers(y, p) % p;
cout << hasil << "\n";
cout << hasil * (y % p) % p << "\n";

Untuk 10 3 1000000007, hasilnya 333.333.339 — dan 333.333.339 × 3 mod 10⁹ + 7 = 10, sesuai.

Uji.

Baris pemeriksaan kedua itulah kebiasaan yang perlu ditiru: sesudah membagi secara modulo, kalikan kembali hasilnya dengan penyebutnya dan pastikan kembali ke nilai semula. Pemeriksaan sependek itu menangkap hampir semua kesalahan invers modulo.

Kesalahan umum.

• Memakai rumus ini untuk p yang bukan prima. Teorema Fermat kecil tidak berlaku; yang dibutuhkan algoritma Euclid diperluas (Bab 15).
• Mencari invers dari y yang habis dibagi p. Invers itu tidak ada, dan rumusnya memberi jawaban yang tidak berarti.
• Menulis x / y % p dengan pembagian bulat biasa. Untuk x = 10, y = 3 itu memberi 3 — jawaban yang sama sekali berbeda.

Latihan bergaya OSN — pembahasan

Berkas jawabannya ada di exercises/14/osn/solutions/.

Soal 1 — Sisa Deret Pangkat

Cara berpikir. Ada N suku, dan setiap suku berupa pangkat dengan eksponen sampai 10⁹. Menghitung satu suku dengan mengalikan K kali berarti 10⁶ × 10⁹ = 10¹⁵ perkalian. Pangkat modulo cepat menurunkannya menjadi sekitar 30 perkalian per suku, sehingga seluruhnya sekitar 3 × 10⁷ — muat. Diukur pada mesin penulis, N = 10⁶ dan K = 10⁹ selesai dalam 0,18 detik.

Pembahasan.

const long long MOD = 1000000007LL;

long long pangkat(long long alas, long long eksponen) {
    long long hasil = 1;
    alas %= MOD;
    while (eksponen > 0) {
        if (eksponen % 2 == 1) hasil = hasil * alas % MOD;
        alas = alas * alas % MOD;
        eksponen /= 2;
    }
    return hasil;
}

// ...
long long total = 0;
for (long long i = 1; i <= n; i++) {
    total = (total + pangkat(i, k)) % MOD;
}

Baris alas %= MOD di awal fungsi bukan hiasan: ia menjamin fungsinya tetap benar walaupun dipanggil dengan alas yang lebih besar daripada modulus.

Uji.

Kesalahan umum.

• Menghitung pangkat dengan perulangan K kali.
• Menjumlahkan dulu semua suku baru mengambil sisanya. Penampungnya meluap jauh sebelum selesai.
• Memakai int di dalam fungsi pangkat, sehingga alas * alas meluap.

Soal 2 — Pangkat Bertingkat

Cara berpikir. Eksponennya, B^C, tidak bisa dihitung sama sekali — untuk B = C = 10⁹ angkanya punya sekitar sembilan miliar digit. Jadi yang diperkecil bukan hasilnya, melainkan eksponennya.

Teorema Fermat kecil menyatakan a^(p−1) ≡ 1 (mod p) untuk p prima dan a bukan kelipatan p. Akibatnya, pangkat a berulang dengan periode p − 1, sehingga

a^e ≡ a^(e mod (p−1))  (mod p)

Jadi langkahnya dua kali pangkat modulo cepat dengan modulus yang berbeda: pertama B^C mod (p − 1) untuk mendapatkan eksponen, lalu A pangkat eksponen itu mod p.

Syarat "A bukan kelipatan p" dijamin oleh batasan A ≤ 10⁹, yang lebih kecil daripada p = 1.000.000.007. Tanpa jaminan itu, langkah ini tidak sah — dan soal OSN yang memakai teknik ini hampir selalu menyertakan batasan serupa.

Pembahasan.

long long eksponen = pangkat(b, c, MOD - 1);
cout << pangkat(a, eksponen, MOD) << "\n";

Karena dipakai dengan dua modulus, fungsi pangkatnya menerima modulus sebagai parameter.

Uji.

Kesalahan umum.

• Menghitung b * c sebagai eksponen. Itu A^(B×C), soal yang berbeda.
• Menyisakan eksponen terhadap MOD, bukan MOD − 1.
• Memakai pangkat(b, c, MOD) untuk eksponennya — modulusnya tertukar, dan hasilnya salah tanpa gejala apa pun.

Soal 3 — Potongan Habis Dibagi K

Cara berpikir. Jumlah potongan A_l sampai A_r sama dengan pre[r] − pre[l−1], seperti pada Bab 10. Jumlah itu habis dibagi K tepat ketika pre[r] dan pre[l−1] bersisa sama jika dibagi K.

Jadi soalnya berubah bentuk: hitung ada berapa pasangan awalan yang bersisa sama. Itu bisa dikerjakan dalam satu kali baca dengan array pencacah sepanjang K: saat sisa baru dihitung, tambahkan banyaknya awalan sebelumnya yang bersisa sama, lalu catat awalan ini.

Awalan kosong — sebelum elemen pertama — juga harus ikut dihitung, karena ia mewakili potongan yang dimulai dari elemen pertama. Karena itu cacah[0] diisi 1 sebelum perulangan.

Bilangan negatif. % di C++ mengikuti tanda bilangan yang dibagi, jadi sisa bisa negatif dan langsung menjadi indeks array di luar batas. Pola ((x % k) + k) % k memperbaikinya.

Pembahasan.

vector<long long> cacah(k, 0);
cacah[0] = 1;                       // awalan kosong

long long sisa = 0, hasil = 0;
for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;

    sisa = ((sisa + x) % k + k) % k;    // tetap tidak negatif
    hasil += cacah[sisa];
    cacah[sisa]++;
}

Perhatikan bahwa sisa tidak pernah menyimpan jumlah sebenarnya, hanya sisanya. Jumlah sebenarnya bisa mencapai 2 × 10¹⁴ dan tidak diperlukan.

Banyaknya potongan pada kasus terburuk — 200.000 angka yang semuanya kelipatan K — mencapai sekitar 2 × 10¹⁰, jadi hasil harus long long.

Uji.

Kasus kedua adalah pemeriksaan cacah[0] = 1: dengan empat angka, seluruh 4 × 5 / 2 = 10 potongan habis dibagi 2. Jawaban 6 berarti awalan kosong tidak dihitung.

Kesalahan umum.

• Lupa cacah[0] = 1, sehingga semua potongan yang dimulai dari elemen pertama tidak terhitung.
• Memakai sisa = (sisa + x) % k tanpa penyesuaian tanda, sehingga program membaca cacah[-2] dan berakhir Runtime Error atau jawaban acak.
• Menyimpan jumlah awalan yang sebenarnya lalu membandingkan berpasangan. Benar, tetapi N² = 4 × 10¹⁰.

Kalau masih tersendat

• Hasil modulo menjadi negatif → Bab 14, bagian Sisa bagi dan fungsi mod_benar.
• Jawaban meluap padahal sudah di-modulo → periksa tipe datanya: perkalian dua bilangan di bawah 10⁹ + 7 harus dikerjakan sebagai long long.
• Pembagian modulo memberi angka yang tidak masuk akal → Bab 14, bagian Teorema Fermat kecil; pembagian dikerjakan dengan invers.

Dua alat bab ini — pangkat modulo cepat dan invers modulo — dipakai lagi di Bab 17 untuk menghitung kombinasi.