// Contoh Bab 15: algoritma Euclid, langkah demi langkah.
//
// Compile:  g++ -std=c++17 -O2 -o fpb exercises/15/01-fpb.cpp
// Jalankan: ./fpb
// Contoh masukan: 48 18
// Coba juga  : 1134903170 701408733  (dua suku Fibonacci berurutan)

#include <iostream>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;

    int langkah = 0;
    cout << "a\tb\ta mod b\n";
    while (b != 0) {
        cout << a << "\t" << b << "\t" << a % b << "\n";
        long long sisa = a % b;
        a = b;
        b = sisa;
        langkah++;
    }

    cout << "FPB = " << a << " (" << langkah << " langkah)\n";
    return 0;
}