Big Integer
多倍長整数, 多倍長
Outline
./Big Integer Class
./Power Mod
多倍長は、配列を用いて整数を表現することで大きな桁数の整数を扱えるように
するものである.
例えば、GNU C++の組み込み型では&mimetex(2^{64});までの整数しか扱えない.
これ以上の桁数を扱いたい場合、double型を使うという裏技もあるが、
普通は多倍長を用いて表現する.
多倍長の仕組みは単純で、配列の各要素に整数を数桁ずつに区切って格納するだけである.
C++では整数を4桁ずつに区切ってshort型の配列を用いるのが効率が良い.
多倍長で面倒なのは四則演算であり、
多倍長と組み込み型、多倍長と多倍長などの演算を独自に定義しなくてはならない.
幸い、C++では演算子のオーバロードが可能であるから、
多倍長クラスを用意すると、透過的に演算を行うことが可能となる.
Big Integer Class?では演算子をオーバロードした多倍長クラスを示す.
ICPCに限って言えば多倍長を使う場面にはあまり出会えないが、
uvaなどでは大量に多倍長問題がある.
多倍長は初めは取っ付きづらいが慣れれば簡単に実装できてしまうので、
しっかりと理解しておく必要がある.
個人的な趣味でいえば、暗号の解読には多倍長は欠かせない(あくまで勉強として).