競技プログラミングにおける多倍長整数問題まとめ

多倍長整数

64ビットを越える整数を扱いたい場合はどうするか

1. 他の解法を考える

• 答えが多倍長整数でもない限り、多倍長整数を使わない解法があったりするのでそれを考える
• 答えが64ビット越えるアレな問題もある(ECR34)

2. 多倍長整数に対応した言語を使う（オススメ！）

• Pythonは対応している
• JavaにはBigIntegerクラスがある

3. 128ビットなら収まりそうという場合は__int128を使う 紹介

• Codeforcesでは使えない

4. Boostのcpp_intを使う 参考

• AtCoder,AOJは使える
• Codeforces,yukicoderでは使えない

5. 自分でライブラリを作る

• Karatsuba法という掛け算を少し高速化する手法がある wikipedia

問題

• ECR34 Almost Difference
• AOJ National Budget
• yukicoder No.167 N^M mod 10 解説
• ARC057 2乗根
• CSA68 Sliding Product Sum 解説
• No.757 チャンパーノウン定数 (2)