본문으로 바로가기

귀납식으로 규칙을 찾은건데, 입력으로 들어오는 모든 수의 최대공배수를 최대공약수로 나누면 답이 나온다.

#include <cstdio>

typedef long long ll;

ll n, x;
ll g, l;

ll GCD(ll, ll);
ll LCM(ll, ll);

int main() {
  scanf("%lld", &n);
  while (n--) {
    scanf("%lld", &x);
    g = !g ? x : GCD(g, x);
    l = !l ? x : LCM(l, x);
  }
  printf("%lld\n", g * l);
  return 0;
}

ll GCD(ll x, ll y) {
  return x % y == 0 ? y : GCD(y, x % y);
}

ll LCM(ll x, ll y) {
  return (x * y) / GCD(x, y);
}

'Programming > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 1076: 저항  (0) 2018.06.11
[BOJ] 1075: 나누기  (0) 2018.06.08
[BOJ] 1037: 약수  (0) 2018.06.08
[BOJ] 1026: 보물  (0) 2018.06.08
[BOJ] 1010: 다리 놓기  (0) 2018.06.05
[BOJ] 1005: ACM Craft  (0) 2018.06.05

댓글을 달아 주세요