競技プログラミングの問題によく出てくる1,000,000,007とか998244353は、どこから出てきた数字なのでしょうか？ | mond

競技プログラミングの問題によく出てくる1,000,000,007とか998244353は、どこから出てきた数字なのでしょうか？ 1,000,000,007や998,244,353は答えの剰余を取るタイプの問題でよく出てくる数ですね。 ① そもそもなぜ剰余を取るのか ② なぜ1,000,000,007がよく使われるのか ③ なぜ998,244,353がよく使われるのか ということに順にお答えすることで元の質問に対する回答になると思うので、それらについてお答えしますね。 ① そもそもなぜ剰余を取るのか そもそもなぜ剰余を取るのが一般的かというと、組み合わせの数を計算する問題では実際の答えの数が32bitさらには64bitの範囲を超えることが一般的で、それらをちゃんと計算するには多倍長整数を扱わないといけないのですが、残念ながら多倍長整数はそれの計算そのものに時間がかかりすぎたり言語によっては取