数論的計算と平方分割を用いた競技プログラミング問題の解説
問題 1：数論的和の計算
この問題では、大きな指数を持つべき乗の和を特定の素数で割った余りを求める必要がある。 naive な快速幂を用いた計算では $O(\sqrt{m} \cdot \log n)$ となり、制限時間を超えてしまう。ここで、法となる数が小さくかつ素数であることに注目する。
フェルマの小定理より、指数部分は法 $p$ に対して $p-1$ で割った余りとして扱ってよい。これに ...
6月1日 04:20 投稿