Kamis, 20 Februari 2014
Faktor Persekutuan Terbesar
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
FPB (Faktor Persekutuan Terbesar) dari dua buah bilangan bulat A dan B adalah bilangan bulat non-negatif terbesar yang membagi A dan membagi B. Misalnya, FPB dari 12 dan 20 adalah 4.
FPB dari dua buah bilangan dapat dicari secara manual. Namun, ada cara yang lebih efisien yaitu menggunakan definisi rekursif sebagai berikut (disebut Algoritma Euclid):
- FPB dari 0 dan suatu bilangan sembarang adalah bilangan sembarang tersebut.
- FPB dari A dan B sama dengan FPB dari B dan (A mod B).
Gunakan definisi rekursif ini untuk membuat sebuah fungsi rekursif yang efisien untuk menghitung FPB dari dua buah bilangan, dan pakailah di dalam program Anda.
Pak Dengklek memberikan Anda T (1 ≤ T ≤ 10.000) pasang bilangan bulat A dan B (0 ≤ A, B ≤ 1.000.000.000). Tentukan FPB dari setiap pasang A dan B tersebut.
Format Masukan
Baris pertama sebuah bilangan bulat T. T baris berikutnya masing-masing berisi dua buah bilangan bulat A dan B.
Format Keluaran
T buah baris, masing-masing berisi sebuah bilangan bulat yaitu FPB dari A dan B.
Contoh Masukan
2 12 20 1 2
Contoh Keluaran
4 1
Pembahasan
