P3934 炸脖龙 I

题面

原题链接 click

题解

典题。
考虑 exEuler 定理，知道指数模 \(\varphi(p)\) 即可知道幂模 \(p\)，线性筛出 \(\varphi\) 函数，发现我们其实只用做 \(O(\log p)\) 次幂运算即可，时间复杂度 \(O(p+m\log^2p\log n)\)，代码略。