15. FPB dan KPK — Pembahasan PR

Berkas .cpp jawabannya ada di exercises/15/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/15/homework/solutions/01-fpb-kpk.cpp
./jawab

Soal 1 — FPB dan KPK

Soal. Cetak FPB lalu KPK dari dua bilangan sampai 10¹⁸.

Cara berpikir. FPB dengan algoritma Euclid, KPK dari sifat FPB × KPK = a × b. Yang diuji di sini adalah urutan operasinya: a / g * b, bukan a * b / g.

Pembahasan.

long long g = fpb(a, b);
cout << g << "\n";
cout << a / g * b << "\n";

Uji.

Baris kedua menguji dua bilangan yang sama: FPB dan KPK-nya sama-sama bilangan itu sendiri. Baris ketiga menguji urutan operasi — dengan a * b / fpb(a, b), perkaliannya meluap jauh sebelum sempat dibagi.

Kesalahan umum.

• Menulis a * b / g. Untuk a dan b berukuran 4 × 10⁹, perkaliannya sudah 1,6 × 10¹⁹ dan meluap sebelum dibagi.
• Memakai faktorisasi prima. Untuk 10¹⁸, memfaktorkan saja sudah terlalu lama; Euclid selesai dalam puluhan langkah.

Soal 2 — Sederhanakan pecahan

Soal. Cetak p/q dalam bentuk paling sederhana.

Cara berpikir. Bagi keduanya dengan FPB-nya. Satu pembagian saja sudah menghasilkan bentuk paling sederhana — tidak perlu diulang, karena setelah dibagi FPB, pembilang dan penyebutnya pasti saling prima.

Pembahasan.

long long g = fpb(p, q);
cout << p / g << "/" << q / g << "\n";

Uji.

Baris ketiga adalah keputusan format yang perlu diperhatikan: soal meminta bentuk p/q, jadi 10/1 yang benar — bukan 10. Kalau soal sungguhan meminta sebaliknya, itu harus disebut di deskripsinya.

Kesalahan umum.

• Membagi berulang dengan 2, 3, 5, … sampai tidak bisa lagi. Benar, tetapi jauh lebih panjang dan mudah salah.
• Lupa bahwa fpb(p, q) tidak pernah nol selama salah satunya positif.

Soal 3 — FPB sederet bilangan

Soal. FPB dari n bilangan.

Cara berpikir. FPB bersifat beruntun: FPB(a, b, c) = FPB(FPB(a, b), c). Nilai awal yang paling rapi adalah 0, karena FPB(0, x) = x — jadi tidak perlu memperlakukan elemen pertama secara khusus.

Data bisa langsung diproses sambil dibaca; array tidak diperlukan.

Pembahasan.

long long g = 0;
for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;
    g = fpb(g, x);
}
cout << g << "\n";

Uji.

Baris ketiga adalah alasan petunjuk di soal: begitu FPB berjalan mencapai 1, sisa datanya tidak perlu diperiksa lagi. Untuk n = 200.000 pemangkasan itu sering menghemat hampir seluruh perulangan.

Kesalahan umum.

• Memulai dengan g = 1. Hasilnya selalu 1.
• Menyimpan seluruh data ke array padahal tidak perlu — bukan kesalahan jawaban, tetapi membuang memori.

Soal 4 — Lampu berkedip

Soal. Detik berikutnya saat semua lampu berkedip bersamaan.

Cara berpikir. Jawabannya KPK dari seluruh selang waktu, dihitung beruntun. Nilai awal 1 tepat di sini, karena KPK(1, x) = x.

Perhatikan bahaya luapan: KPK beruntun membesar dengan cepat. Soal ini membatasi n ≤ 15 dan nilai ≤ 1.000 justru supaya jawabannya tetap muat.

Pembahasan.

long long k = 1;
for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;
    k = kpk(k, x);
}
cout << k << "\n";

Periksa 12 18 8: KPK(1, 12) = 12, KPK(12, 18) = 36, KPK(36, 8) = 72.

Uji.

Baris kedua adalah kesalahan paling khas pada soal ini: mengalikan begitu saja memberi 24, padahal keduanya sudah bertemu di detik ke-12.

Kesalahan umum.

• Memulai k = 0. KPK(0, x) tidak berarti, dan pembagian dengan FPB menghasilkan nol terus.
• Memakai int untuk k.

Tantangan — Invers modulo tanpa Fermat

Soal. Invers a modulo m untuk m sembarang.

Cara berpikir. Teorema Fermat kecil hanya berlaku untuk modulus prima. Untuk m sembarang, pakai Euclid diperluas: ia memberi x dan y dengan

a·x + m·y = FPB(a, m)

Kalau FPB-nya 1, maka modulo m seluruh suku m·y hilang, sehingga a·x ≡ 1 (mod m) — artinya x adalah inversnya. Kalau FPB-nya bukan 1, inversnya memang tidak ada.

x yang dikembalikan bisa negatif, jadi rapikan dengan ((x % m) + m) % m — persis soal 1 Bab 14.

Pembahasan.

long long g = fpb_luas(a, m, x, y);

if (g != 1) {
    cout << "TIDAK ADA\n";
    return 0;
}

long long inv = ((x % m) + m) % m;
cout << inv << "\n";
cout << a % m * inv % m << "\n";

Periksa 3 10: inversnya 7, dan 3 × 7 = 21 ≡ 1 (mod 10). Untuk 4 10 jawabannya TIDAK ADA, karena FPB(4, 10) = 2.

Uji.

Baris kedua adalah alasan soal ini ada: 12 bukan bilangan prima, sehingga teorema Fermat kecil tidak berlaku dan pangkat_mod(a, m - 2, m) akan memberi jawaban yang salah. Euclid diperluas tetap bekerja selama FPB(a, m) = 1.

Kesalahan umum.

• Memakai pangkat_mod(a, m - 2, m) untuk m bukan prima. Hasilnya angka yang kelihatan wajar tetapi salah — dan tidak ada pesan error apa pun. Selalu periksa dengan mengalikan kembali.
• Lupa merapikan x yang negatif.

Latihan bergaya OSN — pembahasan

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

Soal 1 — Ubin Persegi Terbesar

Cara berpikir. Terjemahkan syaratnya satu per satu. "Tidak bersisa ke arah panjang" berarti sisi ubin membagi habis P; "tidak bersisa ke arah lebar" berarti ia juga membagi habis L. Jadi yang dicari adalah pembagi bersama terbesar — kata "terbesar" pada soal langsung menunjuk FPB.

Banyaknya ubin adalah hasil kali jumlah ubin pada kedua arah: (P / sisi) × (L / sisi).

Pembahasan.

long long sisi = fpb(p, l);
long long banyak = (p / sisi) * (l / sisi);

cout << sisi << " " << banyak << "\n";

Batas atas banyaknya ubin adalah P × L = 10¹⁸, yang terjadi ketika FPB-nya

1. Itu muat di long long tetapi tidak di int.

Uji.

Kesalahan umum.

• Memakai bilangan terkecil sebagai sisi ubin. Untuk 12 18 itu memberi 12, yang tidak membagi habis 18.
• Mencari FPB dengan mencoba semua pembagi dari 1 sampai P. Untuk P = 10⁹ itu 10⁹ putaran per kasus.
• Menghitung banyak ubin sebagai p * l / (sisi * sisi). Hasilnya sama, tetapi p * l meluap lebih dulu untuk nilai besar.

Soal 2 — Kelipatan Bersama

Cara berpikir. Sebuah bilangan habis dibagi X sekaligus habis dibagi Y tepat ketika ia habis dibagi KPK(X, Y). Jadi soalnya menjadi: berapa kelipatan L yang berada di antara A dan B?

Banyaknya kelipatan L dari 1 sampai n adalah ⌊n / L⌋. Untuk rentang [A, B], jawabannya ⌊B / L⌋ − ⌊(A − 1) / L⌋. Bentuk A − 1 inilah yang membuat batas kirinya ikut terhitung.

Pembahasan.

long long kpk = x / fpb(x, y) * y;      // bagi dulu, baru kali
long long banyak = b / kpk - (a - 1) / kpk;

Urutan x / fpb * y penting. Dengan x * y / fpb, perkalian 10⁹ × 10⁹ = 10¹⁸ dilakukan lebih dulu — untuk batasan ini masih muat, tetapi kebiasaan itu akan meluap begitu batasannya sedikit dinaikkan.

Uji.

Kesalahan umum.

• Memeriksa setiap bilangan dari A sampai B dengan perulangan.
• Memakai b / kpk - a / kpk, yang melewatkan A sendiri kalau A kebetulan kelipatan KPK.
• Mengalikan X dengan Y sebagai KPK tanpa membagi FPB-nya. Untuk 5 9 3 3 cara itu menjawab 1, bukan 2.

Soal 3 — Pembagi Bersama Selisih

Cara berpikir. Kalimat "bersisa sama" terlihat sulit karena sisanya sendiri tidak diketahui. Ubah sudut pandangnya: kalau Aᵢ dan A_j bersisa sama terhadap d, maka selisihnya habis dibagi d. Sebaliknya juga benar. Jadi syaratnya setara dengan "d membagi habis setiap selisih".

Selisih yang perlu diperiksa cukup terhadap satu bilangan patokan, misalnya A₁. Kalau d membagi habis A₂ − A₁ dan A₃ − A₁, maka ia juga membagi habis A₃ − A₂, karena selisih itu adalah selisih dari dua selisih tadi.

d terbesar yang membagi habis semuanya adalah FPB seluruh selisih.

Nilai awal 0. FPB dihitung bertahap, dan nilai awal yang benar adalah 0 karena fpb(0, x) = x. Nilai awal itu sekaligus menangani kasus khusus: kalau semua bilangannya sama, semua selisihnya 0 dan hasilnya tetap 0 — persis yang diminta soal.

Pembahasan.

long long hasil = 0;
for (int i = 1; i < n; i++) {
    long long selisih = a[i] - a[0];
    if (selisih < 0) selisih = -selisih;
    hasil = fpb(hasil, selisih);
}

cout << hasil << "\n";

Uji.

Kesalahan umum.

• Memulai hasil dari 1, sehingga jawabannya selalu 1.
• Mengambil FPB dari bilangannya sendiri, bukan dari selisihnya. Untuk 5 11 17 cara itu menjawab 1.
• Lupa nilai mutlak kalau patokannya bukan bilangan terkecil.

Kalau masih tersendat

• Bingung memilih FPB atau KPK → Bab 15, bagian Pola soal. "Kapan berulang bersamaan" adalah KPK; "berapa kelompok terbanyak" adalah FPB.
• Jawaban KPK menjadi negatif atau aneh → Bab 15, peringatan tentang urutan operasi.
• Perlu invers modulo tetapi modulusnya bukan prima → Bab 15, bagian Algoritma Euclid diperluas.

Algoritma Euclid hanya empat baris dan dipakai di banyak soal; tulis ulang dari ingatan sampai tidak perlu berpikir lagi.