剰余類の演算
剰余環について
AtCoderの問題で剰余環についてふと思ったので、復習しておきます。
用語
同値類
集合 で同値関係 が定まっているとき、 を を変域とする変数とする。
の空でない部分集合 が
の2つの条件を満たす時、 を同値関係 に関する同値類という。
を法とする剰余類
上の を法とする合同関係 に関する整数 の同値類
を法とする剰余系
の を法とする合同関係 に関する代表系
を法とする剰余集合
商集合
例1) における を法とする剰余集合
剰余類の演算
剰余集合 には和 と積 の演算が定義される。
を を法とする剰余類とし、 の代表元を とする。
と表すと、
が矛盾なく定義される。
例2) を法とする剰余環 における演算
例3) を法とする剰余環について とするとき、 の値
なので
よって、
階乗の余りの計算
以下のAtCoderの問題を解く際に、ある整数 の階乗 を で割った余りを計算する必要がありました。
https://beta.atcoder.jp/contests/abc065/tasks/arc076_a
そのまま を で割った余りを計算すると、 が と大きい場合に の計算結果が膨大になり時間がかかります。JavaであればBigIntegerを使用して結果を求めることは可能です。
ここで剰余類の演算を応用すると
で求められます。
つまり に を掛けたときに除数 を超えたとしても、 によって 未満となり、計算途中の結果が膨大になることが防げ、時間内に結果が得られます。