ALDS1_1_B | Greatest Common Divisor

Calendar Clock iconCalendar Clock icon

AOJ

Table of contents

# Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_B

Given 2 numbers, report the GCD of the 2 numbers.

# Explanation

Euclidean algorithm

# Time complexity

O(log⁡b)O(\log b)

※ bb is the count of modulo arithmetics

# Solution

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;
Int X, Y;

Int gcd(Int x, Int y) {
  if (x > y) swap(x, y);
  
  Int r;
  while (y > 0) {
    r = x % y;
    x = y;
    y = r;
  }
  return x;
}

void input() {
  cin >> X >> Y;
}

void solve() {
  cout << gcd(X, Y) << endl;
}

int main() {
  input();
  solve();
  return 0;
}

Shun

Github Circle icon

Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!

Comments