fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. using namespace std;
  5.  
  6. unsigned gcd(unsigned a, unsigned b, unsigned * const cost) {
  7.   if (cost) {
  8.     *cost = 0;
  9.   }
  10.   while (b != 0) {
  11.     auto const rest = a % b;
  12.     if (cost) {
  13.       ++(*cost);
  14.     }
  15.     a = b;
  16.     b = rest;
  17.   }
  18.   return a;
  19. }
  20.  
  21.  
  22. int main() {
  23.   unsigned const n = 3500;
  24.   unsigned greatestCost = 0;
  25.   vector<pair<unsigned, unsigned>> pairs;
  26.   for (unsigned b = 8; b <= n; ++b) {
  27.     for (unsigned a = 0; a <= b; ++a) {
  28.       unsigned cost;
  29.       gcd(a, b, &cost);
  30.       if (cost == greatestCost) {
  31.         pairs.emplace_back(a, b);
  32.       } else if (cost > greatestCost) {
  33.         pairs.clear();
  34.         pairs.emplace_back(a, b);
  35.         greatestCost = cost;
  36.       }
  37.     }
  38.   }
  39.   cout << "Greatest cost is " << greatestCost << " when calculating the GCD of " << endl;
  40.   for (auto const & p : pairs) {
  41.     cout << "(" << p.first << ", " << p.second  << ")" << endl;
  42.   }
  43.   return 0;
  44. }
Success #stdin #stdout 0.55s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Greatest cost is 17 when calculating the GCD of 
(1597, 2584)
https://ideone.com/t2dS9f
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!