問題

提出解答

問題の概要

$A \times B \times C-D \times E \times F$ を $998244353$ で割った余りを求めよ.

制約

$0 \leq A.B,C,D,E,F \leq 10^{18}$
$A \times B \times C \geq D \times E \times F$

解法

普通に計算しようとする場合, オーバーフローが発生し, 正しく計算できない言語がある. C, C++ などはオーバーフローが発生する言語である. 一方で, Python はオーバーフローが発生しない言語であるから, そのまま計算できる *1 .

整数の余りについて, 整数 $a$ を $m$ で割った余りを $a \pmod{m}$ と書くとき, 次のような性質がある.

$(a+b) \pmod{m}=( (a \pmod{m})+(b \pmod{m})) \pmod{m}$
$(a-b) \pmod{m}=( (a \pmod{m})-(b \pmod{m})) \pmod{m}$
$(a \times b) \pmod{m}=( (a \pmod{m}) \times (b \pmod{m})) \pmod{m}$

このことから, 和の余りは余りの和の余りと等しく, 差, 積についても同様である.

よって, 積の余りを余りの積の積, 差の余りを余りの差の余りにおきかえて計算すればよい.

ただし, $ABC \geq DEF$ は保証されているが, $ABC \pmod{998244353} \geq DEF \pmod{998244353}$ とは限らない. これにより, 負の数の余りの計算が発生する可能性があり, 言語によっては余りが負になってしまう場合があるので, 注意が必要である.

*1:ただし, 計算時間が犠牲になる

Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 275 B問題 ABC-DEF

問題

提出解答

問題の概要

制約

解法