CMR  1.3.0
gcd.hpp
Go to the documentation of this file.
1 #pragma once
2 
3 #include <iostream>
4 
5 namespace tu
6 {
7  template <typename T>
8  T gcd_impl(T a, T b, T& s, T& t)
9  {
10  assert(a >= 0);
11  assert(b >= 0);
12  assert(a >= b);
13 
14  if (b == 0)
15  {
16  s = 1;
17  t = 0;
18  return a;
19  }
20 
21  T q = a / b;
22  T r = a % b;
23  T result = gcd_impl(b, r, t, s);
24  t -= q * s;
25  return result;
26  }
27 
28  template <typename T>
29  T gcd(T a, T b, T& s, T& t)
30  {
31  if (a >= 0 && b >= 0)
32  {
33  if (a >= b)
34  return gcd_impl(a, b, s, t);
35  else
36  return gcd_impl(b, a, t, s);
37  }
38  else
39  {
40  bool a_neg = a < 0;
41  bool b_neg = b < 0;
42  a = a_neg ? -a : a;
43  b = b_neg ? -b : b;
44  assert(a >= 0);
45  assert(b >= 0);
46  T result;
47  if (a >= b)
48  result = gcd_impl(a, b, s, t);
49  else
50  result = gcd_impl(b, a, t, s);
51  if (a_neg)
52  s = -s;
53  if (b_neg)
54  t = -t;
55  assert(result >= 0);
56  return result;
57  }
58  }
59 
60  template <typename T>
61  T gcd(T a, T b)
62  {
63  T s, t;
64  return gcd(a, b, s, t);
65  }
66 } /* namespace tu */
Definition: algorithm.hpp:14
T gcd(T a, T b, T &s, T &t)
Definition: gcd.hpp:29
T gcd_impl(T a, T b, T &s, T &t)
Definition: gcd.hpp:8