test/math/binary-gcd/aoj-ntl-Least-Common-Multiple.test.cpp

• View this file on GitHub
• Last update: 2023-05-29 14:59:47+08:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_C

Depends on

• Binary GCD (位元 GCD) (library/math/binary-gcd.hpp)

Code

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

#include <iostream>
#include "../../../library/math/binary-gcd.hpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	int ans = 1;
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		ans = ans / binary_gcd(ans, x) * x;
	}
	cout << ans << "\n";
	return 0;
}

#line 1 "test/math/binary-gcd/aoj-ntl-Least-Common-Multiple.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_C"

#include <iostream>
#line 2 "library/math/binary-gcd.hpp"

namespace felix {

template<class T>
inline T binary_gcd(T a, T b) {
	if(a == 0 || b == 0) {
		return a | b;
	}
	int8_t n = __builtin_ctzll(a);
	int8_t m = __builtin_ctzll(b);
	a >>= n;
	b >>= m;
	while(a != b) {
		T d = a - b;
		int8_t s = __builtin_ctzll(d);
		bool f = a > b;
		b = f ? b : a;
		a = (f ? d : -d) >> s;
	}
	return a << (n < m ? n : m);
}

} // namespace felix

#line 5 "test/math/binary-gcd/aoj-ntl-Least-Common-Multiple.test.cpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	int ans = 1;
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		ans = ans / binary_gcd(ans, x) * x;
	}
	cout << ans << "\n";
	return 0;
}

Back to top page