038.md

038 - Large LCM (★3)

解答 1

std::lcm(x, y) では整数オーバーフローが発生するケースがあります。

そこで、1 <= A, B のとき lcm(A, B) = A * B / gcd(A, B) であることを利用します。

Large にならないためには
A * B / gcd(A, B) <= (10^18)
である必要があり、それは
B / gcd(A, B) <= 10^18 / a
ということです。

#include <iostream>
#include <numeric> // std::gcd()

int main()
{
	long long A, B;
	std::cin >> A >> B;

	const long long t = (B / std::gcd(A, B));

	if (t <= (1'000'000'000'000'000'000LL / A))
	{
		std::cout << (A * t) << '\n';
	}
	else
	{
		std::cout << "Large\n";
	}
}

解答 2 (多倍長整数ライブラリを使用)

AtCoder では Boost を使えるので、その中の Boost.Multiprecision ライブラリを使うと、問題文のまま工夫せずに解くことができます。boost::multiprecision::cpp_int は任意精度の多倍長整数型です。

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>

int main()
{
	boost::multiprecision::cpp_int A, B;
	std::cin >> A >> B;

	const auto a = boost::multiprecision::lcm(A, B);

	if (1'000'000'000'000'000'000LL < a)
	{
		std::cout << "Large\n";
	}
	else
	{
		std::cout << a << '\n';
	}
}