2023-11-21

競プロ典型 90 問 038 - Large LCM（★3）

オーバーフロー算数と数学易しい整数問題数学(整数問題) 最大公約数 AtCoder 競プロ典型90問競プロ典型90問とその類題競プロ典型90問難易度3

最小公倍数を求める。その際にはオーバーフローに注意！

問題へのリンク

問題概要

正の整数 $A, B$ が与えられる。

$A, B$ の最小公倍数を求めよ。ただし、 $10^{18}$ を超える場合は "Large" と出力せよ。

制約

$1 \le A, B \le 10^{18}$

解法：最大公約数から最小公倍数を求める

まず、整数 $a, b$ の最大公約数を $g$ と書くことにします。このとき、整数 $a, b$ の最小公倍数 $l$ は次のように求められます。

$\displaystyle l = \frac{ab}{g}$

なお、最小公倍数を求めるときには、次のように実装することが多いです。 $a$ も $b$ も $g$ で割り切れるので、 $a$ と $b$ のどちらかを $g$ で割ってから、他方をかけるようにします。次の実装では $a$ を $g$ で割っています。

l = (a / g) * b;

最大公約数の求め方

最大公約数 $g$ は、ユークリッドの互除法によって $O(\log{a} + \log{b})$ の計算量で求められます。C++17 なら関数 gcd(a, b) が使えます。

また、ユークリッドの互助法は次のように実装することもできます。

long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}

ユークリッドの互除法については、次の記事に詳しく書きました。

qiita.com

オーバーフロー対策

ここまでで解けたようにも思えるけれど、C++ の場合、1 つ大きな罠があります (Python3 ならば気にしなくて良いです)。それは、普通に

l = (a / g) * b;

を計算すると、C++ の long long 型を用いるとオーバーフローしてしまう危険性があることです。対策としては、次の 2 つが考えられます。なお、ここで、INF = 1e18 とします。

a / g * b > INF であるかどうかを判定する代わりに、a / g > INF / b であるかどうかを判定する
128 bit 整数を用いる

以下に、これらの方針に基づくコードを示します。計算量はいずれも $O(\log{a} + \log{b})$ となります。

コード

解法 1

#include <bits/stdc++.h>
using namespace std;

// 10^18
const long long INF = 1e18;

int main() {
    long long a, b;
    cin >> a >> b;
    long long g = gcd(a, b);  // C++17 の gcd を利用
    if (a / g > INF / b) cout << "Large" << endl;
    else cout << (a / g) * b << endl;
}

解法 2

128 ビット整数のライブラリを活用しました。__int128 型のラッパーであり、標準入出力などが使えるように準備したものです。

#include <bits/stdc++.h>
using namespace std;

// 128 ビット整数
struct i128 {
    // inner value
    __int128 val;
    
    // constructor
    constexpr i128() : val(0) {}
    constexpr i128(long long v) : val(v) {}
    i128(const string &s) : val(0) {
        parse(s);
    }
    void parse(const string &s) {
        val = 0;
        for (auto c : s) {
            if (isdigit(c)) val = val * 10 + (c - '0');
        }
        if (s[0] == '-') val *= -1;
    }
    constexpr __int128 get() const {
        return val;
    }
    constexpr i128 abs() {
        if (val < 0) return -val;
        else return val;
    }
    
    // comparison operators
    constexpr bool operator == (const i128 &r) const {
        return this->val == r.val;
    }
    constexpr bool operator != (const i128 &r) const {
        return this->val != r.val;
    }
    constexpr bool operator < (const i128 &r) const {
        return this->val < r.val;
    }
    constexpr bool operator > (const i128 &r) const {
        return this->val > r.val;
    }
    constexpr bool operator <= (const i128 &r) const {
        return this->val <= r.val;
    }
    constexpr bool operator >= (const i128 &r) const {
        return this->val >= r.val;
    }
    
    // arithmetic operators
    constexpr i128& operator += (const i128 &r) {
        val += r.val;
        return *this;
    }
    constexpr i128& operator -= (const i128 &r) {
        val -= r.val;
        return *this;
    }
    constexpr i128& operator *= (const i128 &r) {
        val *= r.val;
        return *this;
    }
    constexpr i128& operator /= (const i128 &r) {
        val /= r.val;
        return *this;
    }
    constexpr i128& operator %= (const i128 &r) {
        val %= r.val;
        return *this;
    }
    constexpr i128 operator + () const {
        return i128(*this);
    }
    constexpr i128 operator - () const {
        return i128(0) - i128(*this);
    }
    constexpr i128 operator + (const i128 &r) const {
        return i128(*this) += r;
    }
    constexpr i128 operator - (const i128 &r) const {
        return i128(*this) -= r;
    }
    constexpr i128 operator * (const i128 &r) const {
        return i128(*this) *= r;
    }
    constexpr i128 operator / (const i128 &r) const {
        return i128(*this) /= r;
    }
    constexpr i128 operator % (const i128 &r) const {
        return i128(*this) %= r;
    }
    
    // other operators
    constexpr i128& operator ++ () {
        ++val;
        return *this;
    }
    constexpr i128& operator -- () {
        --val;
        return *this;
    }
    constexpr i128 operator ++ (int) {
        i128 res = *this;
        ++*this;
        return res;
    }
    constexpr i128 operator -- (int) {
        i128 res = *this;
        --*this;
        return res;
    }
    friend istream& operator >> (istream &is, i128 &x) {
        string s;
        is >> s;
        x.parse(s);
        return is;
    }
    friend ostream& operator << (ostream &os, const i128 &x) {
        auto tmp = x.val < 0 ? -x.val : x.val;
        char buffer[128];
        char *d = end(buffer);
        do {
            --d;
            *d = "0123456789"[tmp % 10];
            tmp /= 10;
        } while (tmp != 0);
        if (x.val < 0) {
            --d;
            *d = '-';
        }
        int len = end(buffer) - d;
        if (os.rdbuf()->sputn(d, len) != len) {
            os.setstate(ios_base::badbit);
        }
        return os;
    }
};

// 10^18
const i128 INF = 1e18;

// 最大公約数
i128 GCD(i128 a, i128 b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}

int main() {
    i128 a, b;
    cin >> a >> b;
    
    // 最小公倍数を求める
    i128 l = a / GCD(a, b) * b;
    
    // 出力
    if (l > INF) cout << "Large" << endl;
    else cout << l << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます