整数型とオーバーフロー
Pythonの整数は必要に応じて大きくなります。C++の通常の整数は型ごとに範囲が決まっています。
言語：C++ / 計算量：例の処理による
考え方
- AtCoderの通常環境では int は32bit、long long は64bit。
- 積を取る時点の型に注意します。
- 1LL*a*b で最初から64bit演算にできます。
具体例
int a=100000,b=100000; long long c=a*b; は代入前にintであふれます。c=1LL*a*b; とします。
実装
#include <iostream>
using namespace std;
int main(){
int a=100000,b=100000;
long long c=1LL*a*b;
cout<<c<<"\n";
}注意する条件
符号付き整数のオーバーフローは未定義動作です。あふれてから型変換しても直りません。
確認問題
100000×100000 の正しい値は？
解答と理由
10000000000
10^5×10^5=10^10。32bit符号付き整数の範囲を超えます。
実装課題
int a=50000,b=50000 から、安全に積を求めて出す。入力なし。
出力:
2500000000参考実装
#include <iostream>
using namespace std;
int main(){int a=50000,b=50000;cout<<1LL*a*b<<"\n";}