test/aoj/NTL_1_C.test.cpp

• View this file on GitHub
• Last update: 2021-04-15 20:33:39+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_C

Depends on

• 最大公約数・最小公倍数 (math/euclidean-algorithm.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_C"

#include "../../math/euclidean-algorithm.hpp"
#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  ll ans = 1;
  for (int i = 0; i < n; ++i) {
    ll a;
    cin >> a;
    ans = lcm(ans, a);
  }
  cout << ans << endl;
}

#line 1 "test/aoj/NTL_1_C.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_C"

#line 1 "math/euclidean-algorithm.hpp"
// @title 最大公約数・最小公倍数
#include <cassert>

using ll = long long;

ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
  return a*b / gcd(a, b);
}

#if 0
int main() {
  assert(gcd(18, 24) == 6);
  assert(lcm(18, 24) == 72);
  // aとbの順序が逆でもok
  assert(gcd(7, 3) == 1);
  // aとbの順序が逆でもok
  assert(lcm(7, 3) == 21);
  // intを超える範囲でも問題なく計算できる
  assert(gcd(123456789123456789, 987654321987654321) == 9000000009);
}
#endif
#line 4 "test/aoj/NTL_1_C.test.cpp"
#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  ll ans = 1;
  for (int i = 0; i < n; ++i) {
    ll a;
    cin >> a;
    ans = lcm(ans, a);
  }
  cout << ans << endl;
}

Back to top page