algo — C++23 日本語リファレンス
GitHub

BigInt

クラス · 多倍長整数

struct BigInt;

概要

多倍長整数

内部は基数 $\mathrm{BASE} = 10^6$ のリトルエンディアン配列で保持する。 各桁は $[0, \mathrm{BASE})$ の非負整数で、最上位桁（末尾）が $0$ となる 冗長表現を持たない（値 $0$ は {0} のみ）。符号は sign が表す （負なら true）。ゼロは常に sign == false に正規化される。

構築・破棄

名前 説明 計算量
(constructor) (1) 0を構築する
(2) 64bit整数から構築する
(3) 10進文字列から構築する
(4) 基数BASEの桁列と符号から構築する		 (1) $O(1)$
(2) 桁数を $n$ として $O(n)$
(3) 文字列長を $n$ として $O(n)$
(4) 桁数を $n$ として $O(n)$

メンバ関数

名前 説明 計算量
to_string 10進文字列へ変換する 出力文字数を $n$ として $O(n)$
size 基数BASEでの桁数を返す $O(1)$
is_zero 0か返す $O(1)$
abs 絶対値を返す $O(n)$
abs_less 絶対値の比較 |*this| < |rhs| を返す $O(n)$
div_mod (1) 商と余りを同時に返す
(2) 64bit整数による商と余りを同時に返す		 $O(M(n)\log n)$

演算子

名前 説明 計算量
operator+= rhsを加算する 最大桁数を $n$ として $O(n)$
operator-= rhsを減算する 最大桁数を $n$ として $O(n)$
operator*= (1) rhsを乗算する
(2) 64bit整数を乗算する		 (1) n桁の乗算時間を $M(n)$ として $O(M(n))$
(2) $O(M(n))$
operator/= (1) rhsで除算する
(2) 64bit整数で除算する		 $O(M(n)\log n)$
operator%= (1) rhsによる剰余へ更新する
(2) 64bit整数による剰余へ更新する		 $O(M(n)\log n)$
operator- (1) 符号を反転した値を返す
(2) 差を返す		 $O(n)$
operator+ 和を返す $O(n)$
operator* (1) 積を返す
(2) 64bit整数との積を返す		 $O(M(n))$
operator/ 商を返す $O(M(n)\log n)$
operator% 剰余を返す $O(M(n)\log n)$
operator== 等しいか返す $O(n)$
operator<=> 大小を比較する $O(n)$
operator>> 10進整数を入力する 入力文字数を $n$ として $O(n)$
operator<< 10進整数を出力する 出力文字数を $n$ として $O(n)$

メンバ変数

名前 説明 計算量
BASE — コンパイル時定数で実行時計算量はない
BASE_DIGITS — コンパイル時定数で実行時計算量はない
BZ_THRESHOLD — コンパイル時定数で実行時計算量はない
MUL_2PRIME_MAX_LEN — コンパイル時定数で実行時計算量はない

メンバの詳細

(constructor)

// (1)
BigInt();

// (2)
explicit BigInt(std::int64_t x);

// (3)
explicit BigInt(const std::string &s);

// (4)
explicit BigInt(const std::vector<int> &v, bool flag = false);

(1) 0を構築する

(2) 64bit整数から構築する

(3) 10進文字列から構築する

(4) 基数BASEの桁列と符号から構築する

div_mod

// (1)
std::pair<BigInt, BigInt> div_mod(const BigInt &rhs) const;

// (2)
std::pair<BigInt, BigInt> div_mod(std::int64_t rhs) const;

(1) 商と余りを同時に返す

{*this / rhs, *this % rhs} を返す。除算を 1 回で済ませられる。 余りは被除数 *this と同符号（truncation 方向、operator% と同じ規約）。

(2) 64bit整数による商と余りを同時に返す

operator*=

// (1)
BigInt &operator*=(const BigInt &rhs);

// (2)
BigInt &operator*=(std::int64_t rhs);

(1) rhsを乗算する

(2) 64bit整数を乗算する

operator/=

// (1)
BigInt &operator/=(const BigInt &rhs);

// (2)
BigInt &operator/=(std::int64_t rhs);

(1) rhsで除算する

(2) 64bit整数で除算する

operator%=

// (1)
BigInt &operator%=(const BigInt &rhs);

// (2)
BigInt &operator%=(std::int64_t rhs);

(1) rhsによる剰余へ更新する

(2) 64bit整数による剰余へ更新する

operator-

// (1)
BigInt operator-() const;

// (2)
BigInt operator-(const BigInt &rhs) const;

(1) 符号を反転した値を返す

(2) 差を返す

operator*

// (1)
BigInt operator*(const BigInt &rhs) const;

// (2)
BigInt operator*(std::int64_t rhs) const;

(1) 積を返す

(2) 64bit整数との積を返す

BASE

static constexpr int BASE = 1'000'000;

1 桁が表す基数。10 進 6 桁。

BASE_DIGITS

static constexpr int BASE_DIGITS = 6;

BASE の 10 進桁数。入出力の整形に使う。

BZ_THRESHOLD

static constexpr int BZ_THRESHOLD = 64;

除数がこの桁数以下なら Burnikel-Ziegler 再帰をやめて古典除算に切り替える。

MUL_2PRIME_MAX_LEN

static constexpr int MUL_2PRIME_MAX_LEN = 354659;

乗算で 2 素数 NTT（convolution_ll2）を使える最大畳み込み長。 係数積は高々 $(\mathrm{BASE}-1)^2 \cdot \mathrm{len}$ なので、これが $\mathrm{MOD1} \cdot \mathrm{MOD3}$（約 $3.5 \times 10^{17}$）未満となる $\mathrm{len}$ の上限。 これを超える巨大乗算のみ 3 素数版（convolution_ll）へ落とす。

参照