128 bit 整数型 (internal/int128.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-07-11 16:54:42+09:00
• Include: #include "internal/int128.hpp"

概要

• NicheLibrary::UInt128 は 128 bit 符号なし整数型である。
• NicheLibrary::Int128 は 128 bit 符号付き整数型である。
• GCC 拡張には依存しない。
• std::numeric_limits に対応している。
• 10 進法表記によるストリーム入出力を使用できる。
• 主な用途は、他のライブラリの内部計算型である。
• 組み込み整数型より低速であることに注意する。

使い方

• NicheLibrary::UInt128
  • 128 bit 符号なし整数型である。
  • 整数型から構築できる。
  • 整数型へ明示変換できる。
  • long double へ明示変換できる。
  • 加算、減算、乗算、除算、剰余、比較を使用できる。
  • 10 進法表記によるストリーム入出力を使用できる。
  • 前提: 入力される値が NicheLibrary::UInt128 の範囲に収まる。
  • 前提: 除算と剰余では、除数が $0$ でない。
  • 備考: 演算結果は $2^{128}$ を法として表される。
• NicheLibrary::Int128
  • 128 bit 符号付き整数型である。
  • 整数型から構築できる。
  • 整数型へ明示変換できる。
  • long double へ明示変換できる。
  • 加算、減算、乗算、除算、剰余、比較を使用できる。
  • 10 進法表記によるストリーム入出力を使用できる。
  • 前提: 入力される値が NicheLibrary::Int128 の範囲に収まる。
  • 前提: 演算結果が NicheLibrary::Int128 の範囲に収まる。
  • 前提: 除算と剰余では、除数が $0$ でない。
  • 前提: 型の最小値を $m$ として、 $m / -1$ および $m \bmod -1$ を行わない。
• NicheLibrary::UInt128::div_mod(lhs, rhs, quotient, remainder)
  • lhs を rhs で割った商と余りを求める。
  • 関数の返り値はない。quotient に商を、remainder に余りを書き込む。
  • 前提: rhs は $0$ でない。
  • 備考: lhs を $L$ 、rhs を $R$ 、quotient を $q$ 、remainder を $r$ として、 $L=qR+r$ かつ $0\le r<R$ が成り立つ。
  • 備考: lhs と rhs が同じオブジェクトを参照していてもよい。
  • 備考: quotient や remainder が lhs または rhs と同じオブジェクトを参照していてもよい。
• NicheLibrary::Int128::div_mod(lhs, rhs, quotient, remainder)
  • lhs を rhs で割った商と余りを求める。
  • 関数の返り値はない。quotient に商を、remainder に余りを書き込む。
  • 前提: rhs は $0$ でない。
  • 前提: lhs が型の最小値でないか、または rhs が $-1$ でない。
  • 備考: 商は $0$ 方向へ丸める。
  • 備考: lhs を $L$ 、rhs を $R$ 、quotient を $q$ 、remainder を $r$ として、 $L=qR+r$ が成り立つ。
  • 備考: remainder が $0$ でない場合、remainder の符号は lhs の符号と一致する。
  • 備考: lhs と rhs が同じオブジェクトを参照していてもよい。
  • 備考: quotient や remainder が lhs または rhs と同じオブジェクトを参照していてもよい。
• NicheLibrary::UInt128::from_words(high, low)
  • 上位 64 bit が high、下位 64 bit が low である値を返す。
• NicheLibrary::Int128::from_words(high, low)
  • 2 の補数表現で、上位 64 bit が high、下位 64 bit が low である値を返す。

計算量

• 加算、減算、乗算、比較: 定数回の 64 bit 整数演算を行う。
• 除算、剰余、div_mod: 32 bit の語を用いた固定長の長除算であり、最大で 4 桁の商を求める。
• 10 進法表記のストリーム入出力: 9 桁ごとの処理を最大 5 回行う。

Required by

• 凸包と直線の交点（ $O(\log N)$ ） (geometry/line-convex-polygon-intersection.hpp)
• 一般化 floor sum（次数 2 以下） (math/number-theory/generalized-floor-sum-degree-le-2.hpp)
• $A_i x\equiv B_i\pmod{M_i}$ の形の連立合同方程式 (math/number-theory/generalized-garner.hpp)

Verified with

• verify/aoj-cgl-4-c.test.cpp
• verify/standalone-floor-sum.test.cpp
• verify/standalone-generalized-floor-sum-degree-le-2.test.cpp
• verify/standalone-generalized-garner.test.cpp
• verify/standalone-int128.test.cpp
• verify/standalone-line-convex-polygon-intersection.test.cpp
• verify/yosupo-many-aplusb-128bit.test.cpp
• verify/yukicoder-2117.test.cpp
• verify/yukicoder-2362.test.cpp

Code

#ifndef INTERNAL_INT_ONE_TWO_EIGHT_HPP
#define INTERNAL_INT_ONE_TWO_EIGHT_HPP

// 128 bit 符号なし整数型 UInt128 と 128 bit 符号付き整数型 Int128 を提供する。
// GCC 拡張には依存しない。

#include <bit>
#include <cassert>
#include <cstdint>
#include <istream>
#include <limits>
#include <ostream>
#include <string>
#include <type_traits>

namespace NicheLibrary {
class UInt128 {
  public:
    constexpr UInt128() = default;

    template <
        class T,
        std::enable_if_t<std::is_integral_v<T> && std::is_signed_v<T>, int> = 0>
    constexpr UInt128(T value)
        : high_(value < 0 ? ~std::uint64_t{} : std::uint64_t{}),
          low_(static_cast<std::uint64_t>(value)) {}

    template <class T,
              std::enable_if_t<std::is_integral_v<T> && !std::is_signed_v<T>,
                               int> = 0>
    constexpr UInt128(T value)
        : high_(0), low_(static_cast<std::uint64_t>(value)) {}

    static constexpr UInt128 from_words(std::uint64_t high, std::uint64_t low) {
        UInt128 value;
        value.high_ = high;
        value.low_ = low;
        return value;
    }

    constexpr std::uint64_t high() const { return high_; }
    constexpr std::uint64_t low() const { return low_; }

    template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
    explicit constexpr operator T() const {
        return static_cast<T>(low_);
    }

    explicit constexpr operator bool() const { return high_ != 0 || low_ != 0; }

    explicit constexpr operator long double() const {
        if (high_ == 0) {
            return static_cast<long double>(low_);
        }
        return static_cast<long double>(high_) * 0x1p64L +
               static_cast<long double>(low_);
    }

    friend constexpr bool operator==(UInt128 lhs, UInt128 rhs) {
        return lhs.high_ == rhs.high_ && lhs.low_ == rhs.low_;
    }

    friend constexpr bool operator!=(UInt128 lhs, UInt128 rhs) {
        return !(lhs == rhs);
    }

    friend constexpr bool operator<(UInt128 lhs, UInt128 rhs) {
        if (lhs.high_ != rhs.high_) {
            return lhs.high_ < rhs.high_;
        }
        return lhs.low_ < rhs.low_;
    }

    friend constexpr bool operator>(UInt128 lhs, UInt128 rhs) {
        return rhs < lhs;
    }

    friend constexpr bool operator<=(UInt128 lhs, UInt128 rhs) {
        return !(rhs < lhs);
    }

    friend constexpr bool operator>=(UInt128 lhs, UInt128 rhs) {
        return !(lhs < rhs);
    }

    constexpr UInt128 operator+() const { return *this; }

    constexpr UInt128 operator-() const { return UInt128{} - *this; }

    constexpr UInt128 &operator+=(UInt128 rhs) {
        const std::uint64_t old_low = low_;
        low_ += rhs.low_;
        high_ += rhs.high_ + (low_ < old_low ? 1 : 0);
        return *this;
    }

    constexpr UInt128 &operator-=(UInt128 rhs) {
        const std::uint64_t old_low = low_;
        low_ -= rhs.low_;
        high_ -= rhs.high_ + (old_low < rhs.low_ ? 1 : 0);
        return *this;
    }

    constexpr UInt128 &operator*=(UInt128 rhs) {
        *this = *this * rhs;
        return *this;
    }

    constexpr UInt128 &operator/=(UInt128 rhs) {
        *this = *this / rhs;
        return *this;
    }

    constexpr UInt128 &operator%=(UInt128 rhs) {
        *this = *this % rhs;
        return *this;
    }

    friend constexpr UInt128 operator+(UInt128 lhs, UInt128 rhs) {
        lhs += rhs;
        return lhs;
    }

    friend constexpr UInt128 operator-(UInt128 lhs, UInt128 rhs) {
        lhs -= rhs;
        return lhs;
    }

    friend constexpr UInt128 operator*(UInt128 lhs, UInt128 rhs) {
        const UInt128 p00 = multiply_u64(lhs.low_, rhs.low_);
        return from_words(
            p00.high_ + lhs.low_ * rhs.high_ + lhs.high_ * rhs.low_, p00.low_);
    }

    static constexpr void div_mod(UInt128 lhs, UInt128 rhs, UInt128 &quotient,
                                  UInt128 &remainder) {
        assert(rhs != UInt128{});
        div_mod_unchecked(lhs, rhs, quotient, remainder);
    }

    friend constexpr UInt128 operator/(UInt128 lhs, UInt128 rhs) {
        UInt128 quotient;
        UInt128 remainder;
        div_mod(lhs, rhs, quotient, remainder);
        return quotient;
    }

    friend constexpr UInt128 operator%(UInt128 lhs, UInt128 rhs) {
        UInt128 quotient;
        UInt128 remainder;
        div_mod(lhs, rhs, quotient, remainder);
        return remainder;
    }

  private:
    friend class Int128;

    static constexpr std::uint64_t word_base() {
        return std::uint64_t{1} << 32;
    }

    static constexpr std::uint64_t word_mask() { return word_base() - 1; }

    static constexpr void to_words(UInt128 value, std::uint32_t words[4]) {
        words[0] = static_cast<std::uint32_t>(value.low_ & word_mask());
        words[1] = static_cast<std::uint32_t>(value.low_ >> 32);
        words[2] = static_cast<std::uint32_t>(value.high_ & word_mask());
        words[3] = static_cast<std::uint32_t>(value.high_ >> 32);
    }

    static constexpr UInt128 from_32bit_words(const std::uint32_t words[4]) {
        return UInt128::from_words(
            (static_cast<std::uint64_t>(words[3]) << 32) | words[2],
            (static_cast<std::uint64_t>(words[1]) << 32) | words[0]);
    }

    static constexpr int word_length(const std::uint32_t words[4]) {
        int length = 4;
        while (length > 0 && words[length - 1] == 0) {
            --length;
        }
        return length;
    }

    // divisor ≠ 0 が呼び出し元で保証されていることを仮定する。
    static constexpr UInt128 div_mod_uint32(UInt128 value,
                                            std::uint32_t divisor,
                                            std::uint32_t &remainder) {
        const std::uint32_t words[4] = {
            static_cast<std::uint32_t>(value.low_ & word_mask()),
            static_cast<std::uint32_t>(value.low_ >> 32),
            static_cast<std::uint32_t>(value.high_ & word_mask()),
            static_cast<std::uint32_t>(value.high_ >> 32),
        };

        std::uint32_t quotient_words[4] = {};
        std::uint64_t rem = 0;
        for (int i = 3; i >= 0; --i) {
            const std::uint64_t current = (rem << 32) | words[i];
            quotient_words[i] = static_cast<std::uint32_t>(current / divisor);
            rem = current % divisor;
        }

        remainder = static_cast<std::uint32_t>(rem);
        return from_32bit_words(quotient_words);
    }

    static constexpr void shift_left_words(const std::uint32_t source[4],
                                           int source_length, int shift,
                                           std::uint32_t result[5]) {
        std::uint64_t carry = 0;

        for (int i = 0; i < source_length; ++i) {
            const std::uint64_t current =
                (static_cast<std::uint64_t>(source[i]) << shift) | carry;
            result[i] = static_cast<std::uint32_t>(current & word_mask());
            carry = current >> 32;
        }

        result[source_length] = static_cast<std::uint32_t>(carry);
    }

    static constexpr void shift_right_words(const std::uint32_t source[5],
                                            int source_length, int shift,
                                            std::uint32_t result[4]) {
        if (shift == 0) {
            for (int i = 0; i < source_length; ++i) {
                result[i] = source[i];
            }
            return;
        }

        for (int i = 0; i < source_length; ++i) {
            const std::uint32_t next = i + 1 < 5 ? source[i + 1] : 0;
            result[i] = static_cast<std::uint32_t>(
                (source[i] >> shift) |
                (static_cast<std::uint64_t>(next) << (32 - shift)));
        }
    }

    static constexpr bool subtract_product(std::uint32_t words[5], int offset,
                                           const std::uint32_t divisor[5],
                                           int divisor_length,
                                           std::uint32_t multiplier) {
        std::uint64_t borrow = 0;
        std::uint64_t carry = 0;

        for (int i = 0; i < divisor_length; ++i) {
            const std::uint64_t product =
                static_cast<std::uint64_t>(multiplier) * divisor[i] + carry;
            carry = product >> 32;
            const std::uint64_t subtrahend = (product & word_mask()) + borrow;
            if (static_cast<std::uint64_t>(words[offset + i]) >= subtrahend) {
                words[offset + i] = static_cast<std::uint32_t>(
                    static_cast<std::uint64_t>(words[offset + i]) - subtrahend);
                borrow = 0;
            } else {
                words[offset + i] = static_cast<std::uint32_t>(
                    word_base() + words[offset + i] - subtrahend);
                borrow = 1;
            }
        }

        const std::uint64_t subtrahend = carry + borrow;
        if (static_cast<std::uint64_t>(words[offset + divisor_length]) >=
            subtrahend) {
            words[offset + divisor_length] = static_cast<std::uint32_t>(
                static_cast<std::uint64_t>(words[offset + divisor_length]) -
                subtrahend);
            return false;
        }

        words[offset + divisor_length] = static_cast<std::uint32_t>(
            word_base() + words[offset + divisor_length] - subtrahend);
        return true;
    }

    static constexpr void add_back(std::uint32_t words[5], int offset,
                                   const std::uint32_t divisor[5],
                                   int divisor_length) {
        std::uint64_t carry = 0;
        for (int i = 0; i < divisor_length; ++i) {
            const std::uint64_t sum =
                static_cast<std::uint64_t>(words[offset + i]) + divisor[i] +
                carry;
            words[offset + i] = static_cast<std::uint32_t>(sum & word_mask());
            carry = sum >> 32;
        }

        words[offset + divisor_length] = static_cast<std::uint32_t>(
            static_cast<std::uint64_t>(words[offset + divisor_length]) + carry);
    }

    static constexpr void div_mod_knuth(const std::uint32_t lhs_words[4],
                                        int lhs_length,
                                        const std::uint32_t rhs_words[4],
                                        int rhs_length,
                                        std::uint32_t quotient_words[4],
                                        std::uint32_t remainder_words[4]) {
        const int shift = std::countl_zero(rhs_words[rhs_length - 1]);
        std::uint32_t normalized_lhs[5] = {};
        std::uint32_t normalized_rhs[5] = {};
        shift_left_words(lhs_words, lhs_length, shift, normalized_lhs);
        shift_left_words(rhs_words, rhs_length, shift, normalized_rhs);

        const int quotient_length = lhs_length - rhs_length + 1;
        for (int j = quotient_length - 1; j >= 0; --j) {
            const std::uint64_t numerator =
                (static_cast<std::uint64_t>(normalized_lhs[j + rhs_length])
                 << 32) |
                normalized_lhs[j + rhs_length - 1];
            std::uint64_t estimate = numerator / normalized_rhs[rhs_length - 1];
            std::uint64_t estimate_remainder =
                numerator % normalized_rhs[rhs_length - 1];
            while (estimate == word_base() ||
                   estimate * normalized_rhs[rhs_length - 2] >
                       word_base() * estimate_remainder +
                           normalized_lhs[j + rhs_length - 2]) {
                --estimate;
                estimate_remainder += normalized_rhs[rhs_length - 1];
                if (estimate_remainder >= word_base()) {
                    break;
                }
            }
            quotient_words[j] = static_cast<std::uint32_t>(estimate);
            if (subtract_product(normalized_lhs, j, normalized_rhs, rhs_length,
                                 quotient_words[j])) {
                --quotient_words[j];
                add_back(normalized_lhs, j, normalized_rhs, rhs_length);
            }
        }

        std::uint32_t shifted_remainder[4] = {};
        shift_right_words(normalized_lhs, rhs_length, shift, shifted_remainder);
        for (int i = 0; i < rhs_length; ++i) {
            remainder_words[i] = shifted_remainder[i];
        }
    }

    // 呼び出し元で lhs >= rhs > 0 が保証されていることを仮定する。
    static constexpr void div_mod_32bit_words(UInt128 lhs, UInt128 rhs,
                                              UInt128 &quotient,
                                              UInt128 &remainder) {
        std::uint32_t lhs_words[4] = {};
        std::uint32_t rhs_words[4] = {};
        to_words(lhs, lhs_words);
        to_words(rhs, rhs_words);

        const int lhs_length = word_length(lhs_words);
        const int rhs_length = word_length(rhs_words);

        if (rhs_length == 1) {
            std::uint32_t rem = 0;
            quotient = div_mod_uint32(lhs, rhs_words[0], rem);
            remainder = UInt128(rem);
            return;
        }

        std::uint32_t quotient_words[4] = {};
        std::uint32_t remainder_words[4] = {};
        div_mod_knuth(lhs_words, lhs_length, rhs_words, rhs_length,
                      quotient_words, remainder_words);

        quotient = from_32bit_words(quotient_words);
        remainder = from_32bit_words(remainder_words);
    }

    // rhs ≠ 0 が呼び出し元で保証されていることを仮定する。
    static constexpr void div_mod_unchecked(UInt128 lhs, UInt128 rhs,
                                            UInt128 &quotient,
                                            UInt128 &remainder) {
        UInt128 q, r;
        if (rhs.high_ == 0) {
            if (lhs.high_ == 0) {
                q = UInt128(lhs.low_ / rhs.low_);
                r = UInt128(lhs.low_ % rhs.low_);
            } else if (rhs.low_ == 1) {
                q = lhs;
                r = UInt128{};
            } else if (rhs.low_ <= std::numeric_limits<std::uint32_t>::max()) {
                std::uint32_t rem = 0;
                q = div_mod_uint32(lhs, static_cast<std::uint32_t>(rhs.low_),
                                   rem);
                r = UInt128(rem);
            } else {
                div_mod_32bit_words(lhs, rhs, q, r);
            }
        } else if (lhs < rhs) {
            q = UInt128{};
            r = lhs;
        } else {
            div_mod_32bit_words(lhs, rhs, q, r);
        }
        quotient = q;
        remainder = r;
    }

    static constexpr UInt128 multiply_u64(std::uint64_t lhs,
                                          std::uint64_t rhs) {
        constexpr std::uint64_t mask = (std::uint64_t{1} << 32) - 1;
        const std::uint64_t lhs_low = lhs & mask;
        const std::uint64_t lhs_high = lhs >> 32;
        const std::uint64_t rhs_low = rhs & mask;
        const std::uint64_t rhs_high = rhs >> 32;

        const std::uint64_t p00 = lhs_low * rhs_low;
        const std::uint64_t p01 = lhs_low * rhs_high;
        const std::uint64_t p10 = lhs_high * rhs_low;
        const std::uint64_t p11 = lhs_high * rhs_high;

        const std::uint64_t middle = (p00 >> 32) + (p01 & mask) + (p10 & mask);
        return from_words(p11 + (p01 >> 32) + (p10 >> 32) + (middle >> 32),
                          (middle << 32) | (p00 & mask));
    }

    std::uint64_t high_ = 0;
    std::uint64_t low_ = 0;
};

class Int128 {
  public:
    constexpr Int128() = default;

    template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
    constexpr Int128(T value) : value_(value) {}

    static constexpr Int128 from_words(std::uint64_t high, std::uint64_t low) {
        Int128 value;
        value.value_ = UInt128::from_words(high, low);
        return value;
    }

    constexpr std::uint64_t high() const { return value_.high(); }
    constexpr std::uint64_t low() const { return value_.low(); }

    template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
    explicit constexpr operator T() const {
        return static_cast<T>(value_.low());
    }

    explicit constexpr operator bool() const { return value_ != UInt128{}; }

    constexpr bool is_negative() const { return (value_.high() >> 63) != 0; }

    explicit constexpr operator long double() const {
        const bool negative = is_negative();
        const long double magnitude =
            static_cast<long double>(negative ? -value_ : value_);
        return negative ? -magnitude : magnitude;
    }

    friend constexpr bool operator==(Int128 lhs, Int128 rhs) {
        return lhs.value_ == rhs.value_;
    }

    friend constexpr bool operator!=(Int128 lhs, Int128 rhs) {
        return !(lhs == rhs);
    }

    friend constexpr bool operator<(Int128 lhs, Int128 rhs) {
        const bool lhs_negative = lhs.is_negative();
        const bool rhs_negative = rhs.is_negative();
        if (lhs_negative != rhs_negative) {
            return lhs_negative;
        }
        return lhs.value_ < rhs.value_;
    }

    friend constexpr bool operator>(Int128 lhs, Int128 rhs) {
        return rhs < lhs;
    }

    friend constexpr bool operator<=(Int128 lhs, Int128 rhs) {
        return !(rhs < lhs);
    }

    friend constexpr bool operator>=(Int128 lhs, Int128 rhs) {
        return !(lhs < rhs);
    }

    constexpr Int128 operator+() const { return *this; }

    constexpr Int128 operator-() const {
        Int128 value;
        value.value_ = -value_;
        return value;
    }

    constexpr Int128 &operator+=(Int128 rhs) {
        value_ += rhs.value_;
        return *this;
    }

    constexpr Int128 &operator-=(Int128 rhs) {
        value_ -= rhs.value_;
        return *this;
    }

    constexpr Int128 &operator*=(Int128 rhs) {
        value_ *= rhs.value_;
        return *this;
    }

    constexpr Int128 &operator/=(Int128 rhs) {
        *this = *this / rhs;
        return *this;
    }

    constexpr Int128 &operator%=(Int128 rhs) {
        *this = *this % rhs;
        return *this;
    }

    friend constexpr Int128 operator+(Int128 lhs, Int128 rhs) {
        lhs += rhs;
        return lhs;
    }

    friend constexpr Int128 operator-(Int128 lhs, Int128 rhs) {
        lhs -= rhs;
        return lhs;
    }

    friend constexpr Int128 operator*(Int128 lhs, Int128 rhs) {
        lhs *= rhs;
        return lhs;
    }

    static constexpr void div_mod(Int128 lhs, Int128 rhs, Int128 &quotient,
                                  Int128 &remainder) {
        assert(rhs != Int128{});
        assert(!(lhs == min_value() && rhs == Int128(-1)));

        const bool lhs_negative = lhs.is_negative();
        const bool rhs_negative = rhs.is_negative();
        const bool quotient_negative = lhs_negative != rhs_negative;

        UInt128 quotient_abs;
        UInt128 remainder_abs;
        UInt128::div_mod_unchecked(abs_unsigned(lhs), abs_unsigned(rhs),
                                   quotient_abs, remainder_abs);

        const Int128 q =
            from_unsigned_unchecked(quotient_abs, quotient_negative);
        const Int128 r = from_unsigned_unchecked(remainder_abs, lhs_negative);

        quotient = q;
        remainder = r;
    }

    friend constexpr Int128 operator/(Int128 lhs, Int128 rhs) {
        Int128 quotient;
        Int128 remainder;
        div_mod(lhs, rhs, quotient, remainder);
        return quotient;
    }

    friend constexpr Int128 operator%(Int128 lhs, Int128 rhs) {
        Int128 quotient;
        Int128 remainder;
        div_mod(lhs, rhs, quotient, remainder);
        return remainder;
    }

  private:
    static constexpr Int128 from_twos_complement(UInt128 value) {
        Int128 result;
        result.value_ = value;
        return result;
    }

    static constexpr Int128 min_value() {
        return from_words(std::uint64_t{1} << 63, 0);
    }

    static constexpr UInt128 abs_unsigned(Int128 value) {
        if (!value.is_negative()) {
            return value.value_;
        }
        return -value.value_;
    }

    static constexpr Int128 from_unsigned(UInt128 value, bool negative) {
        if (!negative) {
            assert((value.high() >> 63) == 0);
        } else {
            assert(value <= UInt128::from_words(std::uint64_t{1} << 63, 0));
        }
        return from_unsigned_unchecked(value, negative);
    }

    // 引数 negative で指定した通りに符号を付けた value が
    // Int128 の範囲に収まることを仮定する。
    static constexpr Int128 from_unsigned_unchecked(UInt128 value,
                                                    bool negative) {
        return from_twos_complement(negative ? -value : value);
    }

    friend std::istream &operator>>(std::istream &input, Int128 &value);
    friend std::ostream &operator<<(std::ostream &output, Int128 value);

    UInt128 value_;
};

namespace int128_internal {
// first < text.size() が呼び出し元で保証されていることを仮定する。
inline UInt128 read_uint128_decimal(const std::string &text,
                                    std::size_t first) {
    UInt128 value = 0;

    std::size_t i = first;
    const std::size_t first_len = (text.size() - first) % 9;
    if (first_len != 0) {
        std::uint32_t chunk = 0;
        for (std::size_t j = 0; j < first_len; ++j) {
            assert('0' <= text[i] && text[i] <= '9');
            chunk = chunk * 10 + static_cast<std::uint32_t>(text[i] - '0');
            ++i;
        }
        value = UInt128(chunk);
    }

    while (i < text.size()) {
        std::uint32_t chunk = 0;
        for (int j = 0; j < 9; ++j) {
            assert('0' <= text[i] && text[i] <= '9');
            chunk = chunk * 10 + static_cast<std::uint32_t>(text[i] - '0');
            ++i;
        }
        value *= UInt128(1000000000);
        value += UInt128(chunk);
    }

    return value;
}

inline void write_padded_9(std::ostream &output, std::uint32_t value) {
    char buffer[9];
    for (int i = 8; i >= 0; --i) {
        buffer[i] = static_cast<char>('0' + value % 10);
        value /= 10;
    }
    output.write(buffer, 9);
}

inline void write_uint128_decimal(std::ostream &output, UInt128 value) {
    if (value == UInt128(0)) {
        output << '0';
        return;
    }

    constexpr std::uint32_t base = 1000000000;
    std::uint32_t parts[5] = {};
    int size = 0;
    while (value != UInt128(0)) {
        UInt128 quotient;
        UInt128 remainder;
        UInt128::div_mod(value, UInt128(base), quotient, remainder);
        parts[size] = static_cast<std::uint32_t>(remainder);
        value = quotient;
        ++size;
    }

    output << parts[size - 1];
    for (int i = size - 2; i >= 0; --i) {
        write_padded_9(output, parts[i]);
    }
}
} // namespace int128_internal

inline std::istream &operator>>(std::istream &input, UInt128 &value) {
    std::string text;
    input >> text;
    if (!input) {
        return input;
    }

    std::size_t first = 0;
    if (text[first] == '+') {
        ++first;
    }
    assert(first < text.size());
    assert(text[first] != '-');

    value = int128_internal::read_uint128_decimal(text, first);
    return input;
}

inline std::ostream &operator<<(std::ostream &output, UInt128 value) {
    int128_internal::write_uint128_decimal(output, value);
    return output;
}

inline std::istream &operator>>(std::istream &input, Int128 &value) {
    std::string text;
    input >> text;
    if (!input) {
        return input;
    }

    std::size_t first = 0;
    bool negative = false;
    if (text[first] == '+' || text[first] == '-') {
        negative = text[first] == '-';
        ++first;
    }
    assert(first < text.size());

    const UInt128 magnitude =
        int128_internal::read_uint128_decimal(text, first);
    value = Int128::from_unsigned(magnitude, negative);
    return input;
}

inline std::ostream &operator<<(std::ostream &output, Int128 value) {
    if (value.is_negative()) {
        output << '-';
        int128_internal::write_uint128_decimal(output,
                                               Int128::abs_unsigned(value));
    } else {
        int128_internal::write_uint128_decimal(
            output, UInt128::from_words(value.high(), value.low()));
    }
    return output;
}
} // namespace NicheLibrary

namespace std {
template <> class numeric_limits<NicheLibrary::UInt128> {
  public:
    static constexpr bool is_specialized = true;

    static constexpr NicheLibrary::UInt128 min() noexcept { return 0; }
    static constexpr NicheLibrary::UInt128 max() noexcept {
        return NicheLibrary::UInt128::from_words(~std::uint64_t{},
                                                 ~std::uint64_t{});
    }
    static constexpr NicheLibrary::UInt128 lowest() noexcept { return 0; }

    static constexpr int digits = 128;
    static constexpr int digits10 = 38;
    static constexpr int max_digits10 = 0;
    static constexpr bool is_signed = false;
    static constexpr bool is_integer = true;
    static constexpr bool is_exact = true;
    static constexpr int radix = 2;

    static constexpr NicheLibrary::UInt128 epsilon() noexcept { return 0; }
    static constexpr NicheLibrary::UInt128 round_error() noexcept { return 0; }

    static constexpr int min_exponent = 0;
    static constexpr int min_exponent10 = 0;
    static constexpr int max_exponent = 0;
    static constexpr int max_exponent10 = 0;

    static constexpr bool has_infinity = false;
    static constexpr bool has_quiet_NaN = false;
    static constexpr bool has_signaling_NaN = false;
    static constexpr float_denorm_style has_denorm = denorm_absent;
    static constexpr bool has_denorm_loss = false;

    static constexpr NicheLibrary::UInt128 infinity() noexcept { return 0; }
    static constexpr NicheLibrary::UInt128 quiet_NaN() noexcept { return 0; }
    static constexpr NicheLibrary::UInt128 signaling_NaN() noexcept {
        return 0;
    }
    static constexpr NicheLibrary::UInt128 denorm_min() noexcept { return 0; }

    static constexpr bool is_iec559 = false;
    static constexpr bool is_bounded = true;
    static constexpr bool is_modulo = true;
    static constexpr bool traps = false;
    static constexpr bool tinyness_before = false;
    static constexpr float_round_style round_style = round_toward_zero;
};

template <> class numeric_limits<NicheLibrary::Int128> {
  public:
    static constexpr bool is_specialized = true;

    static constexpr NicheLibrary::Int128 min() noexcept {
        return NicheLibrary::Int128::from_words(std::uint64_t{1} << 63, 0);
    }
    static constexpr NicheLibrary::Int128 max() noexcept {
        return NicheLibrary::Int128::from_words((std::uint64_t{1} << 63) - 1,
                                                ~std::uint64_t{});
    }
    static constexpr NicheLibrary::Int128 lowest() noexcept { return min(); }

    static constexpr int digits = 127;
    static constexpr int digits10 = 38;
    static constexpr int max_digits10 = 0;
    static constexpr bool is_signed = true;
    static constexpr bool is_integer = true;
    static constexpr bool is_exact = true;
    static constexpr int radix = 2;

    static constexpr NicheLibrary::Int128 epsilon() noexcept { return 0; }
    static constexpr NicheLibrary::Int128 round_error() noexcept { return 0; }

    static constexpr int min_exponent = 0;
    static constexpr int min_exponent10 = 0;
    static constexpr int max_exponent = 0;
    static constexpr int max_exponent10 = 0;

    static constexpr bool has_infinity = false;
    static constexpr bool has_quiet_NaN = false;
    static constexpr bool has_signaling_NaN = false;
    static constexpr float_denorm_style has_denorm = denorm_absent;
    static constexpr bool has_denorm_loss = false;

    static constexpr NicheLibrary::Int128 infinity() noexcept { return 0; }
    static constexpr NicheLibrary::Int128 quiet_NaN() noexcept { return 0; }
    static constexpr NicheLibrary::Int128 signaling_NaN() noexcept { return 0; }
    static constexpr NicheLibrary::Int128 denorm_min() noexcept { return 0; }

    static constexpr bool is_iec559 = false;
    static constexpr bool is_bounded = true;
    static constexpr bool is_modulo = false;
    static constexpr bool traps = false;
    static constexpr bool tinyness_before = false;
    static constexpr float_round_style round_style = round_toward_zero;
};
} // namespace std

#endif

#line 1 "internal/int128.hpp"



// 128 bit 符号なし整数型 UInt128 と 128 bit 符号付き整数型 Int128 を提供する。
// GCC 拡張には依存しない。

#include <bit>
#include <cassert>
#include <cstdint>
#include <istream>
#include <limits>
#include <ostream>
#include <string>
#include <type_traits>

namespace NicheLibrary {
class UInt128 {
  public:
    constexpr UInt128() = default;

    template <
        class T,
        std::enable_if_t<std::is_integral_v<T> && std::is_signed_v<T>, int> = 0>
    constexpr UInt128(T value)
        : high_(value < 0 ? ~std::uint64_t{} : std::uint64_t{}),
          low_(static_cast<std::uint64_t>(value)) {}

    template <class T,
              std::enable_if_t<std::is_integral_v<T> && !std::is_signed_v<T>,
                               int> = 0>
    constexpr UInt128(T value)
        : high_(0), low_(static_cast<std::uint64_t>(value)) {}

    static constexpr UInt128 from_words(std::uint64_t high, std::uint64_t low) {
        UInt128 value;
        value.high_ = high;
        value.low_ = low;
        return value;
    }

    constexpr std::uint64_t high() const { return high_; }
    constexpr std::uint64_t low() const { return low_; }

    template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
    explicit constexpr operator T() const {
        return static_cast<T>(low_);
    }

    explicit constexpr operator bool() const { return high_ != 0 || low_ != 0; }

    explicit constexpr operator long double() const {
        if (high_ == 0) {
            return static_cast<long double>(low_);
        }
        return static_cast<long double>(high_) * 0x1p64L +
               static_cast<long double>(low_);
    }

    friend constexpr bool operator==(UInt128 lhs, UInt128 rhs) {
        return lhs.high_ == rhs.high_ && lhs.low_ == rhs.low_;
    }

    friend constexpr bool operator!=(UInt128 lhs, UInt128 rhs) {
        return !(lhs == rhs);
    }

    friend constexpr bool operator<(UInt128 lhs, UInt128 rhs) {
        if (lhs.high_ != rhs.high_) {
            return lhs.high_ < rhs.high_;
        }
        return lhs.low_ < rhs.low_;
    }

    friend constexpr bool operator>(UInt128 lhs, UInt128 rhs) {
        return rhs < lhs;
    }

    friend constexpr bool operator<=(UInt128 lhs, UInt128 rhs) {
        return !(rhs < lhs);
    }

    friend constexpr bool operator>=(UInt128 lhs, UInt128 rhs) {
        return !(lhs < rhs);
    }

    constexpr UInt128 operator+() const { return *this; }

    constexpr UInt128 operator-() const { return UInt128{} - *this; }

    constexpr UInt128 &operator+=(UInt128 rhs) {
        const std::uint64_t old_low = low_;
        low_ += rhs.low_;
        high_ += rhs.high_ + (low_ < old_low ? 1 : 0);
        return *this;
    }

    constexpr UInt128 &operator-=(UInt128 rhs) {
        const std::uint64_t old_low = low_;
        low_ -= rhs.low_;
        high_ -= rhs.high_ + (old_low < rhs.low_ ? 1 : 0);
        return *this;
    }

    constexpr UInt128 &operator*=(UInt128 rhs) {
        *this = *this * rhs;
        return *this;
    }

    constexpr UInt128 &operator/=(UInt128 rhs) {
        *this = *this / rhs;
        return *this;
    }

    constexpr UInt128 &operator%=(UInt128 rhs) {
        *this = *this % rhs;
        return *this;
    }

    friend constexpr UInt128 operator+(UInt128 lhs, UInt128 rhs) {
        lhs += rhs;
        return lhs;
    }

    friend constexpr UInt128 operator-(UInt128 lhs, UInt128 rhs) {
        lhs -= rhs;
        return lhs;
    }

    friend constexpr UInt128 operator*(UInt128 lhs, UInt128 rhs) {
        const UInt128 p00 = multiply_u64(lhs.low_, rhs.low_);
        return from_words(
            p00.high_ + lhs.low_ * rhs.high_ + lhs.high_ * rhs.low_, p00.low_);
    }

    static constexpr void div_mod(UInt128 lhs, UInt128 rhs, UInt128 &quotient,
                                  UInt128 &remainder) {
        assert(rhs != UInt128{});
        div_mod_unchecked(lhs, rhs, quotient, remainder);
    }

    friend constexpr UInt128 operator/(UInt128 lhs, UInt128 rhs) {
        UInt128 quotient;
        UInt128 remainder;
        div_mod(lhs, rhs, quotient, remainder);
        return quotient;
    }

    friend constexpr UInt128 operator%(UInt128 lhs, UInt128 rhs) {
        UInt128 quotient;
        UInt128 remainder;
        div_mod(lhs, rhs, quotient, remainder);
        return remainder;
    }

  private:
    friend class Int128;

    static constexpr std::uint64_t word_base() {
        return std::uint64_t{1} << 32;
    }

    static constexpr std::uint64_t word_mask() { return word_base() - 1; }

    static constexpr void to_words(UInt128 value, std::uint32_t words[4]) {
        words[0] = static_cast<std::uint32_t>(value.low_ & word_mask());
        words[1] = static_cast<std::uint32_t>(value.low_ >> 32);
        words[2] = static_cast<std::uint32_t>(value.high_ & word_mask());
        words[3] = static_cast<std::uint32_t>(value.high_ >> 32);
    }

    static constexpr UInt128 from_32bit_words(const std::uint32_t words[4]) {
        return UInt128::from_words(
            (static_cast<std::uint64_t>(words[3]) << 32) | words[2],
            (static_cast<std::uint64_t>(words[1]) << 32) | words[0]);
    }

    static constexpr int word_length(const std::uint32_t words[4]) {
        int length = 4;
        while (length > 0 && words[length - 1] == 0) {
            --length;
        }
        return length;
    }

    // divisor ≠ 0 が呼び出し元で保証されていることを仮定する。
    static constexpr UInt128 div_mod_uint32(UInt128 value,
                                            std::uint32_t divisor,
                                            std::uint32_t &remainder) {
        const std::uint32_t words[4] = {
            static_cast<std::uint32_t>(value.low_ & word_mask()),
            static_cast<std::uint32_t>(value.low_ >> 32),
            static_cast<std::uint32_t>(value.high_ & word_mask()),
            static_cast<std::uint32_t>(value.high_ >> 32),
        };

        std::uint32_t quotient_words[4] = {};
        std::uint64_t rem = 0;
        for (int i = 3; i >= 0; --i) {
            const std::uint64_t current = (rem << 32) | words[i];
            quotient_words[i] = static_cast<std::uint32_t>(current / divisor);
            rem = current % divisor;
        }

        remainder = static_cast<std::uint32_t>(rem);
        return from_32bit_words(quotient_words);
    }

    static constexpr void shift_left_words(const std::uint32_t source[4],
                                           int source_length, int shift,
                                           std::uint32_t result[5]) {
        std::uint64_t carry = 0;

        for (int i = 0; i < source_length; ++i) {
            const std::uint64_t current =
                (static_cast<std::uint64_t>(source[i]) << shift) | carry;
            result[i] = static_cast<std::uint32_t>(current & word_mask());
            carry = current >> 32;
        }

        result[source_length] = static_cast<std::uint32_t>(carry);
    }

    static constexpr void shift_right_words(const std::uint32_t source[5],
                                            int source_length, int shift,
                                            std::uint32_t result[4]) {
        if (shift == 0) {
            for (int i = 0; i < source_length; ++i) {
                result[i] = source[i];
            }
            return;
        }

        for (int i = 0; i < source_length; ++i) {
            const std::uint32_t next = i + 1 < 5 ? source[i + 1] : 0;
            result[i] = static_cast<std::uint32_t>(
                (source[i] >> shift) |
                (static_cast<std::uint64_t>(next) << (32 - shift)));
        }
    }

    static constexpr bool subtract_product(std::uint32_t words[5], int offset,
                                           const std::uint32_t divisor[5],
                                           int divisor_length,
                                           std::uint32_t multiplier) {
        std::uint64_t borrow = 0;
        std::uint64_t carry = 0;

        for (int i = 0; i < divisor_length; ++i) {
            const std::uint64_t product =
                static_cast<std::uint64_t>(multiplier) * divisor[i] + carry;
            carry = product >> 32;
            const std::uint64_t subtrahend = (product & word_mask()) + borrow;
            if (static_cast<std::uint64_t>(words[offset + i]) >= subtrahend) {
                words[offset + i] = static_cast<std::uint32_t>(
                    static_cast<std::uint64_t>(words[offset + i]) - subtrahend);
                borrow = 0;
            } else {
                words[offset + i] = static_cast<std::uint32_t>(
                    word_base() + words[offset + i] - subtrahend);
                borrow = 1;
            }
        }

        const std::uint64_t subtrahend = carry + borrow;
        if (static_cast<std::uint64_t>(words[offset + divisor_length]) >=
            subtrahend) {
            words[offset + divisor_length] = static_cast<std::uint32_t>(
                static_cast<std::uint64_t>(words[offset + divisor_length]) -
                subtrahend);
            return false;
        }

        words[offset + divisor_length] = static_cast<std::uint32_t>(
            word_base() + words[offset + divisor_length] - subtrahend);
        return true;
    }

    static constexpr void add_back(std::uint32_t words[5], int offset,
                                   const std::uint32_t divisor[5],
                                   int divisor_length) {
        std::uint64_t carry = 0;
        for (int i = 0; i < divisor_length; ++i) {
            const std::uint64_t sum =
                static_cast<std::uint64_t>(words[offset + i]) + divisor[i] +
                carry;
            words[offset + i] = static_cast<std::uint32_t>(sum & word_mask());
            carry = sum >> 32;
        }

        words[offset + divisor_length] = static_cast<std::uint32_t>(
            static_cast<std::uint64_t>(words[offset + divisor_length]) + carry);
    }

    static constexpr void div_mod_knuth(const std::uint32_t lhs_words[4],
                                        int lhs_length,
                                        const std::uint32_t rhs_words[4],
                                        int rhs_length,
                                        std::uint32_t quotient_words[4],
                                        std::uint32_t remainder_words[4]) {
        const int shift = std::countl_zero(rhs_words[rhs_length - 1]);
        std::uint32_t normalized_lhs[5] = {};
        std::uint32_t normalized_rhs[5] = {};
        shift_left_words(lhs_words, lhs_length, shift, normalized_lhs);
        shift_left_words(rhs_words, rhs_length, shift, normalized_rhs);

        const int quotient_length = lhs_length - rhs_length + 1;
        for (int j = quotient_length - 1; j >= 0; --j) {
            const std::uint64_t numerator =
                (static_cast<std::uint64_t>(normalized_lhs[j + rhs_length])
                 << 32) |
                normalized_lhs[j + rhs_length - 1];
            std::uint64_t estimate = numerator / normalized_rhs[rhs_length - 1];
            std::uint64_t estimate_remainder =
                numerator % normalized_rhs[rhs_length - 1];
            while (estimate == word_base() ||
                   estimate * normalized_rhs[rhs_length - 2] >
                       word_base() * estimate_remainder +
                           normalized_lhs[j + rhs_length - 2]) {
                --estimate;
                estimate_remainder += normalized_rhs[rhs_length - 1];
                if (estimate_remainder >= word_base()) {
                    break;
                }
            }
            quotient_words[j] = static_cast<std::uint32_t>(estimate);
            if (subtract_product(normalized_lhs, j, normalized_rhs, rhs_length,
                                 quotient_words[j])) {
                --quotient_words[j];
                add_back(normalized_lhs, j, normalized_rhs, rhs_length);
            }
        }

        std::uint32_t shifted_remainder[4] = {};
        shift_right_words(normalized_lhs, rhs_length, shift, shifted_remainder);
        for (int i = 0; i < rhs_length; ++i) {
            remainder_words[i] = shifted_remainder[i];
        }
    }

    // 呼び出し元で lhs >= rhs > 0 が保証されていることを仮定する。
    static constexpr void div_mod_32bit_words(UInt128 lhs, UInt128 rhs,
                                              UInt128 &quotient,
                                              UInt128 &remainder) {
        std::uint32_t lhs_words[4] = {};
        std::uint32_t rhs_words[4] = {};
        to_words(lhs, lhs_words);
        to_words(rhs, rhs_words);

        const int lhs_length = word_length(lhs_words);
        const int rhs_length = word_length(rhs_words);

        if (rhs_length == 1) {
            std::uint32_t rem = 0;
            quotient = div_mod_uint32(lhs, rhs_words[0], rem);
            remainder = UInt128(rem);
            return;
        }

        std::uint32_t quotient_words[4] = {};
        std::uint32_t remainder_words[4] = {};
        div_mod_knuth(lhs_words, lhs_length, rhs_words, rhs_length,
                      quotient_words, remainder_words);

        quotient = from_32bit_words(quotient_words);
        remainder = from_32bit_words(remainder_words);
    }

    // rhs ≠ 0 が呼び出し元で保証されていることを仮定する。
    static constexpr void div_mod_unchecked(UInt128 lhs, UInt128 rhs,
                                            UInt128 &quotient,
                                            UInt128 &remainder) {
        UInt128 q, r;
        if (rhs.high_ == 0) {
            if (lhs.high_ == 0) {
                q = UInt128(lhs.low_ / rhs.low_);
                r = UInt128(lhs.low_ % rhs.low_);
            } else if (rhs.low_ == 1) {
                q = lhs;
                r = UInt128{};
            } else if (rhs.low_ <= std::numeric_limits<std::uint32_t>::max()) {
                std::uint32_t rem = 0;
                q = div_mod_uint32(lhs, static_cast<std::uint32_t>(rhs.low_),
                                   rem);
                r = UInt128(rem);
            } else {
                div_mod_32bit_words(lhs, rhs, q, r);
            }
        } else if (lhs < rhs) {
            q = UInt128{};
            r = lhs;
        } else {
            div_mod_32bit_words(lhs, rhs, q, r);
        }
        quotient = q;
        remainder = r;
    }

    static constexpr UInt128 multiply_u64(std::uint64_t lhs,
                                          std::uint64_t rhs) {
        constexpr std::uint64_t mask = (std::uint64_t{1} << 32) - 1;
        const std::uint64_t lhs_low = lhs & mask;
        const std::uint64_t lhs_high = lhs >> 32;
        const std::uint64_t rhs_low = rhs & mask;
        const std::uint64_t rhs_high = rhs >> 32;

        const std::uint64_t p00 = lhs_low * rhs_low;
        const std::uint64_t p01 = lhs_low * rhs_high;
        const std::uint64_t p10 = lhs_high * rhs_low;
        const std::uint64_t p11 = lhs_high * rhs_high;

        const std::uint64_t middle = (p00 >> 32) + (p01 & mask) + (p10 & mask);
        return from_words(p11 + (p01 >> 32) + (p10 >> 32) + (middle >> 32),
                          (middle << 32) | (p00 & mask));
    }

    std::uint64_t high_ = 0;
    std::uint64_t low_ = 0;
};

class Int128 {
  public:
    constexpr Int128() = default;

    template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
    constexpr Int128(T value) : value_(value) {}

    static constexpr Int128 from_words(std::uint64_t high, std::uint64_t low) {
        Int128 value;
        value.value_ = UInt128::from_words(high, low);
        return value;
    }

    constexpr std::uint64_t high() const { return value_.high(); }
    constexpr std::uint64_t low() const { return value_.low(); }

    template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
    explicit constexpr operator T() const {
        return static_cast<T>(value_.low());
    }

    explicit constexpr operator bool() const { return value_ != UInt128{}; }

    constexpr bool is_negative() const { return (value_.high() >> 63) != 0; }

    explicit constexpr operator long double() const {
        const bool negative = is_negative();
        const long double magnitude =
            static_cast<long double>(negative ? -value_ : value_);
        return negative ? -magnitude : magnitude;
    }

    friend constexpr bool operator==(Int128 lhs, Int128 rhs) {
        return lhs.value_ == rhs.value_;
    }

    friend constexpr bool operator!=(Int128 lhs, Int128 rhs) {
        return !(lhs == rhs);
    }

    friend constexpr bool operator<(Int128 lhs, Int128 rhs) {
        const bool lhs_negative = lhs.is_negative();
        const bool rhs_negative = rhs.is_negative();
        if (lhs_negative != rhs_negative) {
            return lhs_negative;
        }
        return lhs.value_ < rhs.value_;
    }

    friend constexpr bool operator>(Int128 lhs, Int128 rhs) {
        return rhs < lhs;
    }

    friend constexpr bool operator<=(Int128 lhs, Int128 rhs) {
        return !(rhs < lhs);
    }

    friend constexpr bool operator>=(Int128 lhs, Int128 rhs) {
        return !(lhs < rhs);
    }

    constexpr Int128 operator+() const { return *this; }

    constexpr Int128 operator-() const {
        Int128 value;
        value.value_ = -value_;
        return value;
    }

    constexpr Int128 &operator+=(Int128 rhs) {
        value_ += rhs.value_;
        return *this;
    }

    constexpr Int128 &operator-=(Int128 rhs) {
        value_ -= rhs.value_;
        return *this;
    }

    constexpr Int128 &operator*=(Int128 rhs) {
        value_ *= rhs.value_;
        return *this;
    }

    constexpr Int128 &operator/=(Int128 rhs) {
        *this = *this / rhs;
        return *this;
    }

    constexpr Int128 &operator%=(Int128 rhs) {
        *this = *this % rhs;
        return *this;
    }

    friend constexpr Int128 operator+(Int128 lhs, Int128 rhs) {
        lhs += rhs;
        return lhs;
    }

    friend constexpr Int128 operator-(Int128 lhs, Int128 rhs) {
        lhs -= rhs;
        return lhs;
    }

    friend constexpr Int128 operator*(Int128 lhs, Int128 rhs) {
        lhs *= rhs;
        return lhs;
    }

    static constexpr void div_mod(Int128 lhs, Int128 rhs, Int128 &quotient,
                                  Int128 &remainder) {
        assert(rhs != Int128{});
        assert(!(lhs == min_value() && rhs == Int128(-1)));

        const bool lhs_negative = lhs.is_negative();
        const bool rhs_negative = rhs.is_negative();
        const bool quotient_negative = lhs_negative != rhs_negative;

        UInt128 quotient_abs;
        UInt128 remainder_abs;
        UInt128::div_mod_unchecked(abs_unsigned(lhs), abs_unsigned(rhs),
                                   quotient_abs, remainder_abs);

        const Int128 q =
            from_unsigned_unchecked(quotient_abs, quotient_negative);
        const Int128 r = from_unsigned_unchecked(remainder_abs, lhs_negative);

        quotient = q;
        remainder = r;
    }

    friend constexpr Int128 operator/(Int128 lhs, Int128 rhs) {
        Int128 quotient;
        Int128 remainder;
        div_mod(lhs, rhs, quotient, remainder);
        return quotient;
    }

    friend constexpr Int128 operator%(Int128 lhs, Int128 rhs) {
        Int128 quotient;
        Int128 remainder;
        div_mod(lhs, rhs, quotient, remainder);
        return remainder;
    }

  private:
    static constexpr Int128 from_twos_complement(UInt128 value) {
        Int128 result;
        result.value_ = value;
        return result;
    }

    static constexpr Int128 min_value() {
        return from_words(std::uint64_t{1} << 63, 0);
    }

    static constexpr UInt128 abs_unsigned(Int128 value) {
        if (!value.is_negative()) {
            return value.value_;
        }
        return -value.value_;
    }

    static constexpr Int128 from_unsigned(UInt128 value, bool negative) {
        if (!negative) {
            assert((value.high() >> 63) == 0);
        } else {
            assert(value <= UInt128::from_words(std::uint64_t{1} << 63, 0));
        }
        return from_unsigned_unchecked(value, negative);
    }

    // 引数 negative で指定した通りに符号を付けた value が
    // Int128 の範囲に収まることを仮定する。
    static constexpr Int128 from_unsigned_unchecked(UInt128 value,
                                                    bool negative) {
        return from_twos_complement(negative ? -value : value);
    }

    friend std::istream &operator>>(std::istream &input, Int128 &value);
    friend std::ostream &operator<<(std::ostream &output, Int128 value);

    UInt128 value_;
};

namespace int128_internal {
// first < text.size() が呼び出し元で保証されていることを仮定する。
inline UInt128 read_uint128_decimal(const std::string &text,
                                    std::size_t first) {
    UInt128 value = 0;

    std::size_t i = first;
    const std::size_t first_len = (text.size() - first) % 9;
    if (first_len != 0) {
        std::uint32_t chunk = 0;
        for (std::size_t j = 0; j < first_len; ++j) {
            assert('0' <= text[i] && text[i] <= '9');
            chunk = chunk * 10 + static_cast<std::uint32_t>(text[i] - '0');
            ++i;
        }
        value = UInt128(chunk);
    }

    while (i < text.size()) {
        std::uint32_t chunk = 0;
        for (int j = 0; j < 9; ++j) {
            assert('0' <= text[i] && text[i] <= '9');
            chunk = chunk * 10 + static_cast<std::uint32_t>(text[i] - '0');
            ++i;
        }
        value *= UInt128(1000000000);
        value += UInt128(chunk);
    }

    return value;
}

inline void write_padded_9(std::ostream &output, std::uint32_t value) {
    char buffer[9];
    for (int i = 8; i >= 0; --i) {
        buffer[i] = static_cast<char>('0' + value % 10);
        value /= 10;
    }
    output.write(buffer, 9);
}

inline void write_uint128_decimal(std::ostream &output, UInt128 value) {
    if (value == UInt128(0)) {
        output << '0';
        return;
    }

    constexpr std::uint32_t base = 1000000000;
    std::uint32_t parts[5] = {};
    int size = 0;
    while (value != UInt128(0)) {
        UInt128 quotient;
        UInt128 remainder;
        UInt128::div_mod(value, UInt128(base), quotient, remainder);
        parts[size] = static_cast<std::uint32_t>(remainder);
        value = quotient;
        ++size;
    }

    output << parts[size - 1];
    for (int i = size - 2; i >= 0; --i) {
        write_padded_9(output, parts[i]);
    }
}
} // namespace int128_internal

inline std::istream &operator>>(std::istream &input, UInt128 &value) {
    std::string text;
    input >> text;
    if (!input) {
        return input;
    }

    std::size_t first = 0;
    if (text[first] == '+') {
        ++first;
    }
    assert(first < text.size());
    assert(text[first] != '-');

    value = int128_internal::read_uint128_decimal(text, first);
    return input;
}

inline std::ostream &operator<<(std::ostream &output, UInt128 value) {
    int128_internal::write_uint128_decimal(output, value);
    return output;
}

inline std::istream &operator>>(std::istream &input, Int128 &value) {
    std::string text;
    input >> text;
    if (!input) {
        return input;
    }

    std::size_t first = 0;
    bool negative = false;
    if (text[first] == '+' || text[first] == '-') {
        negative = text[first] == '-';
        ++first;
    }
    assert(first < text.size());

    const UInt128 magnitude =
        int128_internal::read_uint128_decimal(text, first);
    value = Int128::from_unsigned(magnitude, negative);
    return input;
}

inline std::ostream &operator<<(std::ostream &output, Int128 value) {
    if (value.is_negative()) {
        output << '-';
        int128_internal::write_uint128_decimal(output,
                                               Int128::abs_unsigned(value));
    } else {
        int128_internal::write_uint128_decimal(
            output, UInt128::from_words(value.high(), value.low()));
    }
    return output;
}
} // namespace NicheLibrary

namespace std {
template <> class numeric_limits<NicheLibrary::UInt128> {
  public:
    static constexpr bool is_specialized = true;

    static constexpr NicheLibrary::UInt128 min() noexcept { return 0; }
    static constexpr NicheLibrary::UInt128 max() noexcept {
        return NicheLibrary::UInt128::from_words(~std::uint64_t{},
                                                 ~std::uint64_t{});
    }
    static constexpr NicheLibrary::UInt128 lowest() noexcept { return 0; }

    static constexpr int digits = 128;
    static constexpr int digits10 = 38;
    static constexpr int max_digits10 = 0;
    static constexpr bool is_signed = false;
    static constexpr bool is_integer = true;
    static constexpr bool is_exact = true;
    static constexpr int radix = 2;

    static constexpr NicheLibrary::UInt128 epsilon() noexcept { return 0; }
    static constexpr NicheLibrary::UInt128 round_error() noexcept { return 0; }

    static constexpr int min_exponent = 0;
    static constexpr int min_exponent10 = 0;
    static constexpr int max_exponent = 0;
    static constexpr int max_exponent10 = 0;

    static constexpr bool has_infinity = false;
    static constexpr bool has_quiet_NaN = false;
    static constexpr bool has_signaling_NaN = false;
    static constexpr float_denorm_style has_denorm = denorm_absent;
    static constexpr bool has_denorm_loss = false;

    static constexpr NicheLibrary::UInt128 infinity() noexcept { return 0; }
    static constexpr NicheLibrary::UInt128 quiet_NaN() noexcept { return 0; }
    static constexpr NicheLibrary::UInt128 signaling_NaN() noexcept {
        return 0;
    }
    static constexpr NicheLibrary::UInt128 denorm_min() noexcept { return 0; }

    static constexpr bool is_iec559 = false;
    static constexpr bool is_bounded = true;
    static constexpr bool is_modulo = true;
    static constexpr bool traps = false;
    static constexpr bool tinyness_before = false;
    static constexpr float_round_style round_style = round_toward_zero;
};

template <> class numeric_limits<NicheLibrary::Int128> {
  public:
    static constexpr bool is_specialized = true;

    static constexpr NicheLibrary::Int128 min() noexcept {
        return NicheLibrary::Int128::from_words(std::uint64_t{1} << 63, 0);
    }
    static constexpr NicheLibrary::Int128 max() noexcept {
        return NicheLibrary::Int128::from_words((std::uint64_t{1} << 63) - 1,
                                                ~std::uint64_t{});
    }
    static constexpr NicheLibrary::Int128 lowest() noexcept { return min(); }

    static constexpr int digits = 127;
    static constexpr int digits10 = 38;
    static constexpr int max_digits10 = 0;
    static constexpr bool is_signed = true;
    static constexpr bool is_integer = true;
    static constexpr bool is_exact = true;
    static constexpr int radix = 2;

    static constexpr NicheLibrary::Int128 epsilon() noexcept { return 0; }
    static constexpr NicheLibrary::Int128 round_error() noexcept { return 0; }

    static constexpr int min_exponent = 0;
    static constexpr int min_exponent10 = 0;
    static constexpr int max_exponent = 0;
    static constexpr int max_exponent10 = 0;

    static constexpr bool has_infinity = false;
    static constexpr bool has_quiet_NaN = false;
    static constexpr bool has_signaling_NaN = false;
    static constexpr float_denorm_style has_denorm = denorm_absent;
    static constexpr bool has_denorm_loss = false;

    static constexpr NicheLibrary::Int128 infinity() noexcept { return 0; }
    static constexpr NicheLibrary::Int128 quiet_NaN() noexcept { return 0; }
    static constexpr NicheLibrary::Int128 signaling_NaN() noexcept { return 0; }
    static constexpr NicheLibrary::Int128 denorm_min() noexcept { return 0; }

    static constexpr bool is_iec559 = false;
    static constexpr bool is_bounded = true;
    static constexpr bool is_modulo = false;
    static constexpr bool traps = false;
    static constexpr bool tinyness_before = false;
    static constexpr float_round_style round_style = round_toward_zero;
};
} // namespace std

Back to top page