#include <iostream>
using namespace std;
int gcd(int u, int v, int &num_iterations)
{
num_iterations++;
if (v==0)
return u;
else
return gcd(v, u%v, num_iterations);
}
int gcd_slow(int u, int v, int &num_iterations)
{
int low = min(u,v);
int high = max(u,v);
for (int k=low; k>0; k=k-1)
{
num_iterations++;
if ( (low%k == 0) && (high%k == 0) )
return k;
}
}
int main()
{
int i;
int j;
int num_euclid = 0;
int num_slow = 0;
int my_gcd;
// read numbers from input
cin >> i;
cin >> j;
// compute GCD
my_gcd = gcd(i, j, num_euclid);
cout << "gcd(" << i << "," << j << ") = " << my_gcd << endl;
cout << "number of iterations of Euclid's algorithm: " << num_euclid << endl;
my_gcd = gcd_slow(i, j, num_slow);
cout << "gcd(" << i << "," << j << ") = " << my_gcd << endl;
cout << "number of iterations of the slow algorithm: " << num_slow << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBnY2QoaW50IHUsIGludCB2LCBpbnQgJm51bV9pdGVyYXRpb25zKQp7CiAgIG51bV9pdGVyYXRpb25zKys7CgogICBpZiAodj09MCkKICAgICByZXR1cm4gdTsKICAgZWxzZQogICAgIHJldHVybiBnY2QodiwgdSV2LCBudW1faXRlcmF0aW9ucyk7Cn0KCmludCBnY2Rfc2xvdyhpbnQgdSwgaW50IHYsIGludCAmbnVtX2l0ZXJhdGlvbnMpCnsKICAgaW50IGxvdyA9IG1pbih1LHYpOwogICBpbnQgaGlnaCA9IG1heCh1LHYpOwogCiAgIGZvciAoaW50IGs9bG93OyBrPjA7IGs9ay0xKQogICAgIHsKICAgICAgIG51bV9pdGVyYXRpb25zKys7CiAgICAgICBpZiAoIChsb3clayA9PSAwKSAmJiAoaGlnaCVrID09IDApICkKICAgICAgICAgIHJldHVybiBrOwogICAgIH0KfQoKCmludCBtYWluKCkKewogIGludCBpOwogIGludCBqOwogIGludCBudW1fZXVjbGlkID0gMDsKICBpbnQgbnVtX3Nsb3cgICA9IDA7CgogIGludCBteV9nY2Q7CgogIC8vIHJlYWQgbnVtYmVycyBmcm9tIGlucHV0CgogIGNpbiA+PiBpOwogIGNpbiA+PiBqOwoKICAvLyBjb21wdXRlIEdDRAoKICBteV9nY2QgPSBnY2QoaSwgaiwgbnVtX2V1Y2xpZCk7CgogIGNvdXQgPDwgImdjZCgiIDw8IGkgPDwgIiwiIDw8IGogPDwgIikgPSAiIDw8IG15X2djZCA8PCBlbmRsOwogIGNvdXQgPDwgIm51bWJlciBvZiBpdGVyYXRpb25zIG9mIEV1Y2xpZCdzIGFsZ29yaXRobTogIiA8PCBudW1fZXVjbGlkIDw8IGVuZGw7CgogIG15X2djZCA9IGdjZF9zbG93KGksIGosIG51bV9zbG93KTsKCiAgY291dCA8PCAiZ2NkKCIgPDwgaSA8PCAiLCIgPDwgaiA8PCAiKSA9ICIgPDwgbXlfZ2NkIDw8IGVuZGw7CiAgY291dCA8PCAibnVtYmVyIG9mIGl0ZXJhdGlvbnMgb2YgdGhlIHNsb3cgYWxnb3JpdGhtOiAiIDw8IG51bV9zbG93IDw8IGVuZGw7CgogIHJldHVybiAwOwp9