-
Notifications
You must be signed in to change notification settings - Fork 12
/
LCM.cpp
51 lines (40 loc) · 1.09 KB
/
LCM.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//
// LCM (最小公倍数)
//
// cf.
// 拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜
// https://qiita.com/drken/items/b97ff231e43bce50199a
//
// verified
// ABC 070 C - Multiple Clocks
// https://beta.atcoder.jp/contests/abc070/tasks/abc070_c
//
/*
a と b の最大公約数を G、最小公倍数を L とすると
GL = ab
が成り立つ。よって、
L = a/g * b (a は g で割り切れる)
注意点として、L = a*b/g としてしまうと a*b の計算する部分でオーバーフローの危険がある。
*/
#include <iostream>
using namespace std;
long long GCD(long long a, long long b) {
if (b == 0) return a;
else return GCD(b, a % b);
}
long long LCM(long long a, long long b) {
long long g = GCD(a, b);
return a / g * b;
}
//------------------------------//
// Examples
//------------------------------//
int main() {
int N; cin >> N;
long long res = 1;
for (int i = 0; i < N; ++i) {
long long a; cin >> a;
res = LCM(res, a);
}
cout << res << endl;
}