競技プログラミングにおける剰余

aとｂのmod Mが等しいことを、aとbはMを法として合同という

aとbがMを法として合同であることと、a - b = kMを満たす整数kが存在することは同値

これはaとbをMで割った余りが等しいことと同値

a = pM + r, b = qM + r とすると a - b = (p - q)M

r = a - pMなので、この定義だと

こちらの定義の方が使いやすい

足し算、掛け算、引き算では計算途中でmodをとった場合と、計算後にmodをとった場合とで結果が一致する

a - b = kMを満たすkが存在するとき、