// Contoh Bab 15: KPK dari FPB, dan bahaya urutan operasi.
//
// Compile:  g++ -std=c++17 -O2 -o kpk exercises/15/02-kpk.cpp
// Jalankan: ./kpk

#include <iostream>
using namespace std;

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

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

int main() {
    cout << "KPK(12, 18)  = " << kpk_aman(12, 18) << "\n";
    cout << "KPK(4, 6)    = " << kpk_aman(4, 6) << "\n";

    // Dua bilangan besar.
    long long a = 4000000000LL, b = 6000000000LL;
    cout << "KPK besar    = " << kpk_aman(a, b) << "\n";

    // Versi berbahaya: a * b dihitung lebih dulu, padahal 2,4 * 10^19
    // melewati batas long long (sekitar 9,2 * 10^18).
    cout << "a * b        = " << a * b << "  (meluap, nilainya salah)\n";
    cout << "a / fpb * b  = " << a / fpb(a, b) * b << "  (benar)\n";

    // KPK beruntun 1..20
    long long k = 1;
    for (int i = 1; i <= 20; i++) k = kpk_aman(k, i);
    cout << "KPK 1..20    = " << k << "\n";
    return 0;
}