#include <iostream>
#include <vector>
#include <utility>
using namespace std;
unsigned gcd(unsigned a, unsigned b, unsigned * const cost) {
if (cost) {
*cost = 0;
}
while (b != 0) {
auto const rest = a % b;
if (cost) {
++(*cost);
}
a = b;
b = rest;
}
return a;
}
int main() {
unsigned const n = 3500;
unsigned greatestCost = 0;
vector<pair<unsigned, unsigned>> pairs;
for (unsigned b = 8; b <= n; ++b) {
for (unsigned a = 0; a <= b; ++a) {
unsigned cost;
gcd(a, b, &cost);
if (cost == greatestCost) {
pairs.emplace_back(a, b);
} else if (cost > greatestCost) {
pairs.clear();
pairs.emplace_back(a, b);
greatestCost = cost;
}
}
}
cout << "Greatest cost is " << greatestCost << " when calculating the GCD of " << endl;
for (auto const & p : pairs) {
cout << "(" << p.first << ", " << p.second << ")" << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8dXRpbGl0eT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnVuc2lnbmVkIGdjZCh1bnNpZ25lZCBhLCB1bnNpZ25lZCBiLCB1bnNpZ25lZCAqIGNvbnN0IGNvc3QpIHsKICBpZiAoY29zdCkgewogICAgKmNvc3QgPSAwOwogIH0KICB3aGlsZSAoYiAhPSAwKSB7CiAgICBhdXRvIGNvbnN0IHJlc3QgPSBhICUgYjsKICAgIGlmIChjb3N0KSB7CiAgICAgICsrKCpjb3N0KTsKICAgIH0KICAgIGEgPSBiOwogICAgYiA9IHJlc3Q7CiAgfQogIHJldHVybiBhOwp9CgoKaW50IG1haW4oKSB7CiAgdW5zaWduZWQgY29uc3QgbiA9IDM1MDA7CiAgdW5zaWduZWQgZ3JlYXRlc3RDb3N0ID0gMDsKICB2ZWN0b3I8cGFpcjx1bnNpZ25lZCwgdW5zaWduZWQ+PiBwYWlyczsKICBmb3IgKHVuc2lnbmVkIGIgPSA4OyBiIDw9IG47ICsrYikgewogICAgZm9yICh1bnNpZ25lZCBhID0gMDsgYSA8PSBiOyArK2EpIHsKICAgICAgdW5zaWduZWQgY29zdDsKICAgICAgZ2NkKGEsIGIsICZjb3N0KTsKICAgICAgaWYgKGNvc3QgPT0gZ3JlYXRlc3RDb3N0KSB7CiAgICAgICAgcGFpcnMuZW1wbGFjZV9iYWNrKGEsIGIpOwogICAgICB9IGVsc2UgaWYgKGNvc3QgPiBncmVhdGVzdENvc3QpIHsKICAgICAgICBwYWlycy5jbGVhcigpOwogICAgICAgIHBhaXJzLmVtcGxhY2VfYmFjayhhLCBiKTsKICAgICAgICBncmVhdGVzdENvc3QgPSBjb3N0OwogICAgICB9CiAgICB9CiAgfQogIGNvdXQgPDwgIkdyZWF0ZXN0IGNvc3QgaXMgIiA8PCBncmVhdGVzdENvc3QgPDwgIiB3aGVuIGNhbGN1bGF0aW5nIHRoZSBHQ0Qgb2YgIiA8PCBlbmRsOwogIGZvciAoYXV0byBjb25zdCAmIHAgOiBwYWlycykgewogICAgY291dCA8PCAiKCIgPDwgcC5maXJzdCA8PCAiLCAiIDw8IHAuc2Vjb25kICA8PCAiKSIgPDwgZW5kbDsKICB9CiAgcmV0dXJuIDA7Cn0=