プログラミングコンテストチャレンジブック 4-1 その1

4-1 「より複雑な数学的問題」からです。

  • 連立一時方程式
  • mod の世界
    • N を法とした世界で ay = 1 (mod N) となる a の逆元
      • ax - Nk = 1 となる x を探せばよい
    • フェルマーの小定理
      • 任意の素数 p について x^(p-1) == 1 (mod p)