「998244353 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita

1. なぜ 998244353 で割るのか？ 最初はこのような設問を見るとぎょっとしてしまいますが、実はとても自然な問題設定です。 $998244353$ で割らないと、答えの桁数がとてつもなく大きくなってしまうことがあります。このとき以下のような問題が生じます: 多倍長整数がサポートされている言語とされていない言語とで有利不利が生じる 10000 桁にも及ぶような巨大な整数を扱うとなると計算時間が膨大にかかってしまう 1 番目の事情はプログラミングコンテストに特有のものと思えなくもないですが、2 番目の事情は切実です。整数の足し算や掛け算などを実施するとき、桁数があまりにも大きくなると桁数に応じた計算時間がかかってしまいます。実用的にもそのような巨大な整数を扱うときは、いくつかの素数で割ったあまりを計算しておいて、最後に中国剰余定理を適用して復元することも多いです。 なぜ 9982443

[UDONCHAN]

“10910910^9 より大きい最小の素数で、手頃な素数である”

[ING40]

1000000007 で割る理由。

[labocho]

atcoder mint

[gogatsu26]

擬人化して十億ナナちゃんと呼ぼう

[aya_momo]

「Python であってもその都度 1000000007で割るのを怠ると桁数が大きくなって計算時間が増大してしまいます」いや、数十桁くらいなら割らない方が速いことが多いだろう。

[programmablekinoko]

素晴らしい