中国剰余定理
- 中国風剰余問題、中国人剰余問題、CRT : Chinese Remainder Theorem
- 表記ゆらぎがむっちゃあるのでCRTで統一した方がいいんじゃないかと思ってる
- 解説
- 解ける問題
ある数m1,m2,...,mnとある数a1,a2,...,anがあり、 x ≡ a1 (mod m1) x ≡ a2 (mod m2) … x ≡ an (mod mn) であることが分かっている時、これを満たすx(mod m1*m2*...*mn)を導出する
- 素数でないmod計算をこれを使って解くテクがある これの発展的話題はこのテクを使っている
