15. FPB dan KPK

FPB (faktor persekutuan terbesar) dan KPK (kelipatan persekutuan terkecil) muncul di soal OSN dalam banyak samaran: membagi barang sama rata, menyederhanakan pecahan, mencari kapan dua kejadian berulang bersamaan. Bab ini membahas cara menghitungnya dengan cepat.

Pengertian

• FPB(a, b) adalah bilangan terbesar yang membagi habis a dan b.
• KPK(a, b) adalah bilangan positif terkecil yang habis dibagi a dan b.

Contoh untuk 12 dan 18:

Pembagi bersama terbesar: 6. Kelipatan bersama terkecil: 36.

Cara sekolah dasar — faktorkan menjadi bilangan prima, ambil pangkat terkecil untuk FPB dan terbesar untuk KPK — benar, tetapi lambat: untuk a sampai 10¹⁸, memfaktorkan saja sudah memakan waktu terlalu lama.

Algoritma Euclid

Cara cepatnya berumur lebih dari dua ribu tahun dan hanya memakai satu sifat:

FPB(a, b) = FPB(b, a mod b), dan FPB(a, 0) = a.

Alasannya: setiap pembagi bersama a dan b juga membagi a − b, dan karena itu juga membagi a mod b. Jadi himpunan pembagi bersamanya tidak berubah, sementara angkanya mengecil dengan cepat.

Gambaran yang membantu: bayangkan persegi panjang berukuran a × b yang ingin ditutup ubin persegi sama besar tanpa dipotong. Potong persegi sebesar b × b sebanyak mungkin dari ujungnya; sisa yang tertinggal berukuran (a mod b) × b. Ubin yang bisa menutup persegi panjang semula persis ubin yang bisa menutup sisanya — karena bagian yang dipotong tadi sudah pasti bisa ditutup. Mengulang pemotongan itu sampai sisanya habis memberi ukuran ubin terbesar, yaitu FPB.

Telusuri FPB(48, 18):

Jawabannya 6.

Versi rekursif:

long long fpb(long long a, long long b) {
    if (b == 0) return a;
    return fpb(b, a % b);
}

Versi perulangan:

long long fpb(long long a, long long b) {
    while (b != 0) {
        long long sisa = a % b;
        a = b;
        b = sisa;
    }
    return a;
}

Satu contoh lagi, FPB(1071, 462):

Jawabannya 21. Perhatikan betapa cepat angkanya menyusut: setiap dua langkah, bilangan yang lebih besar setidaknya berkurang separuh.

Jumlah langkahnya O(log min(a, b)) — untuk bilangan sebesar 10¹⁸ pun kurang dari 90 langkah. Pasangan yang paling "keras kepala" adalah dua bilangan Fibonacci berurutan: untuk 1.134.903.170 dan 701.408.733, algoritmanya memerlukan 43 langkah, dan itu sudah yang terburuk pada rentang miliaran. Bandingkan dengan cara sekolah dasar yang perlu memfaktorkan kedua bilangan lebih dulu — untuk bilangan sebesar itu, pemfaktorannya saja sudah jauh lebih lama daripada seluruh algoritma Euclid.

KPK dari FPB

Sifat yang menghubungkan keduanya:

FPB(a, b) × KPK(a, b) = a × b

Jadi:

long long kpk(long long a, long long b) {
    return a / fpb(a, b) * b;        // bagi dulu, baru kali
}

Periksa dengan contoh 12 dan 18: FPB-nya 6, dan 12 / 6 × 18 = 2 × 18 = 36 — cocok dengan tabel di awal bab.

FPB dan KPK banyak bilangan

Keduanya bisa dihitung beruntun:

long long g = a[0];
for (int i = 1; i < n; i++) g = fpb(g, a[i]);

long long k = a[0];
for (int i = 1; i < n; i++) k = kpk(k, a[i]);

FPB beruntun aman, dan bahkan bisa berhenti lebih awal: begitu nilainya mencapai 1, hasilnya tidak mungkin berubah lagi.

KPK beruntun cepat meluap: KPK dari 1 sampai 20 saja sudah 232.792.560, dan KPK dari 1 sampai 43 sudah melewati batas long long. Karena itu soal biasanya meminta KPK modulo suatu bilangan, atau membatasi datanya.

Pola soal

Menyederhanakan pecahan. Bagi pembilang dan penyebut dengan FPB-nya.

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

Kejadian berulang. Lampu A berkedip tiap 12 detik, lampu B tiap 18 detik. Keduanya berkedip bersamaan tiap KPK(12, 18) = 36 detik.

Membagi rata. Ada 48 permen dan 18 cokelat, dibagikan sama rata tanpa sisa ke sebanyak mungkin anak: FPB(48, 18) = 6 anak.

Ubin persegi. Lantai 48 × 18 cm ditutup ubin persegi sama besar tanpa dipotong: sisi terbesarnya FPB(48, 18) = 6 cm.

Bilangan saling prima. a dan b disebut saling prima kalau FPB(a, b) = 1. Ini syarat yang sering muncul, misalnya pada invers modulo.

Algoritma Euclid diperluas

Versi lanjut yang tidak hanya menghitung FPB, tetapi juga mencari x dan y yang memenuhi:

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

long long fpb_luas(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = fpb_luas(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

Contohnya untuk a = 3 dan b = 7: algoritmanya menghasilkan x = -2 dan y = 1, dan benar bahwa 3 × (−2) + 7 × 1 = 1. Karena suku 7 · y tidak menyumbang apa pun modulo 7, berarti 3 × (−2) ≡ 1 (mod 7), sehingga invers 3 modulo 7 adalah −2, yang dirapikan menjadi ((-2 % 7) + 7) % 7 = 5. Periksa: 3 × 5 = 15 = 2 × 7 + 1. Benar.

Gunanya: mencari invers modulo ketika modulusnya bukan bilangan prima, sehingga teorema Fermat kecil (Bab 14) tidak berlaku. Kalau FPB(a, m) = 1, maka dari a·x + m·y = 1 diperoleh a·x ≡ 1 (mod m), jadi x adalah invers a.

Pekerjaan rumah

Kesalahan yang paling sering

Tips OSN

Kenali isyarat FPB dan KPK dari kalimat soalnya. Kedua kata ini jarang muncul apa adanya di soal OSN; yang muncul adalah ceritanya.

Tulis KPK sebagai a / fpb(a, b) * b, bukan a * b / fpb(a, b). Keduanya benar secara matematika, tetapi bentuk kedua menghitung a * b lebih dulu dan bisa meluap padahal KPK-nya sendiri kecil. Membagi lebih dulu selalu pas, karena FPB pasti membagi habis a.

KPK bisa meledak, FPB tidak pernah. FPB selalu tidak lebih besar daripada bilangan terkecilnya, tetapi KPK beberapa bilangan bisa tumbuh sangat cepat: KPK dari 1 sampai 20 saja sudah lebih dari 2 × 10⁸. Kalau soal meminta KPK banyak bilangan tanpa modulo, periksa batasannya — sering kali yang diminta sebenarnya jawabannya modulo sesuatu, atau batasannya memang kecil.

Algoritma Euclid sangat cepat, jadi jangan diganti. Mencari FPB dengan mencoba semua pembagi memerlukan sampai 10⁹ langkah untuk bilangan sebesar itu; Euclid menyelesaikannya dalam puluhan langkah. Perbedaannya bukan optimasi, melainkan mungkin dan tidak mungkin.

FPB sederet bilangan dihitung bertahap. fpb(a, b, c) sama dengan fpb(fpb(a, b), c), dan sifat ini berlaku untuk berapa pun bilangannya. Nilai awal yang benar adalah 0, karena fpb(0, x) = x. Memulai dari 1 adalah kesalahan yang membuat semua jawaban menjadi 1.

Selisih adalah petunjuk tersembunyi. Soal yang berbunyi "semua bilangan bersisa sama jika dibagi d" sebenarnya berbicara tentang selisih: d harus membagi habis setiap selisih. Perubahan sudut pandang ini mengubah soal yang tampak sulit menjadi satu baris FPB.

Ringkasan

• FPB(a, b) adalah pembagi bersama terbesar, KPK(a, b) kelipatan bersama terkecil.
• Algoritma Euclid: FPB(a, b) = FPB(b, a mod b), berhenti saat b = 0. Memerlukan O(log min(a, b)) langkah.
• KPK dihitung dari FPB: a / fpb(a, b) * b — bagi dulu, baru kali, supaya tidak meluap.
• FPB beruntun aman dan bisa berhenti begitu mencapai 1; KPK beruntun cepat meluap.
• Pola soalnya: menyederhanakan pecahan (FPB), kejadian berulang bersamaan (KPK), membagi rata ke sebanyak mungkin kelompok (FPB), ubin persegi terbesar (FPB).
• Euclid diperluas mencari x dan y pada a·x + b·y = FPB(a, b), dan dipakai untuk invers modulo saat modulusnya bukan prima.

Latihan bergaya OSN

Ketiga soal berikut tidak pernah menyebut kata FPB atau KPK. Bagian yang dilatih justru itu: mengenali alat yang dimaksud dari kalimat ceritanya.

Kerangka ketiganya ada di exercises/15/osn/.

Soal 1 — Ubin Persegi Terbesar

Sebuah lantai berbentuk persegi panjang berukuran P × L sentimeter akan ditutup ubin berbentuk persegi yang semuanya berukuran sama. Ubin tidak boleh dipotong, tidak boleh bertumpuk, dan lantainya harus tertutup penuh tanpa sisa sedikit pun.

Tentukan sisi ubin terbesar yang memenuhi syarat itu, dan berapa ubin yang terpakai.

Format masukan. Satu baris berisi dua bilangan bulat P dan L.

Format keluaran. Satu baris berisi dua bilangan bulat: sisi ubin terbesar dan banyaknya ubin, dipisahkan satu spasi.

Batasan. 1 ≤ P, L ≤ 10⁹.

Contoh masukan

12 18

Contoh keluaran

6 6

Penjelasan. Sisi ubin harus membagi habis 12 maupun 18. Pilihan yang mungkin adalah 1, 2, 3, dan 6; yang terbesar adalah 6. Dengan ubin 6 × 6, lantainya terbagi menjadi 2 × 3 = 6 ubin.

Kerangkanya: exercises/15/osn/01-ubin-persegi.cpp

Soal 2 — Kelipatan Bersama

Sebuah pabrik punya dua mesin. Mesin pertama berbunyi pada setiap detik yang merupakan kelipatan X, dan mesin kedua pada setiap detik yang merupakan kelipatan Y. Hitung ada berapa detik di antara detik A dan detik B, termasuk keduanya, saat kedua mesin berbunyi bersamaan.

Format masukan. Satu baris berisi empat bilangan bulat A, B, X, dan Y.

Format keluaran. Satu baris berisi banyaknya detik tersebut.

Batasan.

• 1 ≤ A ≤ B ≤ 10¹⁸
• 1 ≤ X, Y ≤ 10⁹

Contoh masukan

1 100 4 6

Contoh keluaran

8

Penjelasan. Kedua mesin berbunyi bersamaan pada detik 12, 24, 36, 48, 60, 72, 84, dan 96 — ada delapan. Perhatikan batasan B: memeriksa setiap detik satu per satu tidak mungkin.

Kerangkanya: exercises/15/osn/02-kelipatan-bersama.cpp

Soal 3 — Pembagi Bersama Selisih

Diberikan N bilangan bulat. Carilah bilangan bulat positif d terbesar sehingga seluruh bilangan itu memberikan sisa yang sama jika masing- masing dibagi d.

Kalau semua bilangannya sama persis, d boleh bernilai berapa pun; untuk kasus itu cetak 0.

Format masukan. Baris pertama berisi bilangan bulat N. Baris kedua berisi N bilangan bulat.

Format keluaran. Satu baris berisi d terbesar, atau 0 untuk kasus khusus di atas.

Batasan.

• 2 ≤ N ≤ 200.000
• 1 ≤ Aᵢ ≤ 10¹⁸

Contoh masukan

3
5 11 17

Contoh keluaran

6

Penjelasan. Dengan d = 6, ketiga bilangan bersisa 5. Tidak ada d yang lebih besar yang memberi sisa sama untuk ketiganya.

Kerangkanya: exercises/15/osn/03-pembagi-selisih.cpp

Bingung atau sudah selesai? Buka halaman pembahasan PR.