CMR
1.3.0
src
cmr
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 */
tu
Definition:
algorithm.hpp:14
tu::gcd
T gcd(T a, T b, T &s, T &t)
Definition:
gcd.hpp:29
tu::gcd_impl
T gcd_impl(T a, T b, T &s, T &t)
Definition:
gcd.hpp:8
Generated by
1.9.1