競プロ典型90問 038(★3) オーバーフロー

038 - Large LCM（★3）

問題

A, Bの最小公倍数を求める。

を超える場合は Large と出力する。

解法

最小公倍数は で表される。

そのまま計算すると でオーバーフローすることがあるので、式を変換する。

であれば が成り立つので正しく答えが求まる。

ちなみに Boost Multiprecision Library を使うと、多倍長整数の計算が扱えるのでそのまま計算するだけで良い。

所感

オーバーフローや誤差などの数字を扱う問題は、ちょっとした気付きで解ける事が多い気がする。

Boostの存在を知れたので良かった。

計算に時間がかかるのでそこは注意したい。

コード

実行時間(3 ms)

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
const int INF = (int)1e9;
const ll INFL = (ll)1e18;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
int dx[]={0, 0, -1, 1};
int dy[]={1, -1, 0, 0};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main()
{
    ll a, b;
    cin >> a >> b;
    ll t = b / gcd(a, b);
    if (t > INFL / a) cout << "Large" << endl;
    else cout << t * b << endl;
    return 0;
}

boost を使った解法

実行時間 (12ms)

#include <bits/stdc++.h>
using namespace std;
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;

int main()
{
    Bint a, b, ans = 0;
    cin >> a >> b;
    ans = lcm(a, b);
    if (ans > (int64_t)1e18) cout << "Large" << endl;
    else cout << ans << endl;
    return 0;
}