掛け算のオーバーフロー問題
競プロの復習をしている際に、9桁×9桁の計算でそれを1e9+7の余りを出すという問題があった。
9桁では1e9+7であらかじめ余りを出すことはできず、for文で一つずつ足すことも考えたが9桁分(10億回)ループを回すのはあほらしい。
何が原因だったか
わかれば滅茶苦茶簡単な理由だった。
今までプログラムを書いてきて、ほとんどintで済ませてきていたため、今回の問題もintで進めていた。
intの最大値は約2.1e9なので、もちろん9桁同士の掛け算はオーバーフローを起こす。
解決方法
解決方法は単純明快、intを使わなければいいだけの話。
intからlong long intに型を変更した。
long long int型は最大値が約9.2e18なので9桁同士の掛け算は余裕ですることができる。
型を変更したことで、簡単に答えを出すことができた。
結果
普段使わない型もしっかりと把握しておけば問題ない。
こんな簡単なことに数時間気付かなく恥ずかしい...