二完でした。
Clown Fiesta
解説AC。
「オイラーのφ関数」に関する理解が乏しかった。
Editorialにある次の式は覚えておいてもいいと思う。
・$a^b = a^{b \,\,\mathrm{mod}\,\, \varphi (m)}(\mathrm{mod}\,\,m)$
・$a^{b^c} = a^{b^{c \,\, \mathrm{mod}\,\,\varphi (\varphi (m))} \,\,\mathrm{mod} \,\,\varphi (m)}(\mathrm{mod}\,\,m)$
（もちろん、「覚えておいてもいい」は言葉の綾で、「オイラーのφ関数を使う」ということさえ記憶しておけば導出は簡単なので覚える必要はない）
これをふまえると、mod mで考えるとき、ベキ乗の肩にたくさんの数が乗っていても途中から（それも、mが小さければ結構すぐに）無視できるということになる。（この問題もそれを利用して解く）
競技プログラミングをやっていれば知っていて当然の知識だろうけど、ちょっと驚いた。
0 件のコメント:
コメントを投稿