test/aoj/NTL_1_C/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_C
• Link: View error logs on GitHub Actions

Depends on

• Input vector (Mylib/IO/input_vector.cpp)
• Binary GCD (Mylib/Number/binary_gcd.cpp)

Code

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

#include <iostream>
#include <vector>
#include "Mylib/IO/input_vector.cpp"
#include "Mylib/Number/binary_gcd.cpp"

namespace hl = haar_lib;

int main() {
  int n;
  std::cin >> n;

  auto a = hl::input_vector<int>(n);

  int l = 1;
  for (auto x : a) {
    l = l / hl::binary_gcd(l, x) * x;
  }

  std::cout << l << "\n";

  return 0;
}

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

#include <iostream>
#include <vector>
#line 4 "Mylib/IO/input_vector.cpp"

namespace haar_lib {
  template <typename T>
  std::vector<T> input_vector(int N) {
    std::vector<T> ret(N);
    for (int i = 0; i < N; ++i) std::cin >> ret[i];
    return ret;
  }

  template <typename T>
  std::vector<std::vector<T>> input_vector(int N, int M) {
    std::vector<std::vector<T>> ret(N);
    for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
    return ret;
  }
}  // namespace haar_lib
#line 2 "Mylib/Number/binary_gcd.cpp"
#include <cmath>
#include <utility>

namespace haar_lib {
  int64_t binary_gcd(int64_t a, int64_t b) {
    int64_t g = 1;

    while (1) {
      if (a > b) std::swap(a, b);

      if (a == 0) {
        break;
      } else {
        if ((a & 1) == 0 and (b & 1) == 0) {
          a >>= 1;
          b >>= 1;
          g <<= 1;
        } else if ((a & 1) == 0) {
          a >>= 1;
        } else if ((b & 1) == 0) {
          b >>= 1;
        } else {
          int64_t t = std::abs(a - b) >> 1;
          b         = t;
        }
      }
    }

    return g * b;
  }
}  // namespace haar_lib
#line 7 "test/aoj/NTL_1_C/main.test.cpp"

namespace hl = haar_lib;

int main() {
  int n;
  std::cin >> n;

  auto a = hl::input_vector<int>(n);

  int l = 1;
  for (auto x : a) {
    l = l / hl::binary_gcd(l, x) * x;
  }

  std::cout << l << "\n";

  return 0;
}

Back to top page