以下、$f(x,y,z)=x^y\ {\rm mod} \ z$として、一般論について述べた上で、今回のケースへの適用方法を示す。

$x$と$z$に共通する素因数を$p_1,p_2,\cdots p_k$とし、$z=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}u$（ただし、$u$は$p_1,p_2,\cdots p_k$のいずれとも互いに素な整数）とする。この時、$p_1^{e_1},p_2^{e_2},\cdots p_k^{e_k},u$は全て互いに素な整数となるので、$f(x,y,z)$の値を求める場合、$f(x,y,p_1^{e_1}),f(x,y,p_2^{e_2}),\cdots f(x,y,p_k^{e_k}),f(x,y,u)$の値を求めれば良い。

$f(x,y,p_i^{e_i})\ \ (i=1,2,\cdots k)$の求め方

$x$が$p_i$で割れる回数を$v_i$とすると、$v_iy\geq e_i$ならば$f(x,y,p_i^{e_i})=0$であり、$v_iy<e_i$ならば$f(x,y,p_i^{e_i})=p_i^{v_iy}$である。

今回の場合、$f(a,a\uparrow\uparrow (n-1),p_i^{e_i})$を求めれば良い。$a\uparrow\uparrow (n-1)$の値は多くの場合とてつもなく大きな値になるが、今回の場合は$v_i\cdot a\uparrow\uparrow (n-1)$と$e_i$の大小関係さえ分かれば良い。

$x_i$は$p_i$を素因数に持つので、$v_i\geq 1$である。また、$z\geq p_i^{e_i}$より$10^9\geq 2^{e_i}$なので、$e_i\leq \log_2{10^9}=29.8\cdots$より$e_i\leq 29$である。よって、$v_i\cdot a\uparrow\uparrow (n-1)<e_i$ならば$a\uparrow\uparrow (n-1)<29$なので、$a\uparrow\uparrow (n-1)\leq 28$となるケースについてのみ考えれば良い。

$a\uparrow\uparrow (n-1)\leq 28$となる$(a,n)$の組は以下の通り。

よって、これらの組に該当するならば$v_i\cdot a\uparrow\uparrow (n-1)$の値を直接計算すれば良い。また、該当しないならば$v_i\cdot a\uparrow\uparrow (n-1)\geq e_i$となる。

$f(x,y,u)$の求め方

$x$と$u$は互いに素であるから、オイラーの定理より$x^{\varphi (u)}\equiv 1\ ({\rm mod}\ u)$である。（$\varphi (u)$はオイラーのφ関数）　よって、$y\ {\rm mod}\ \varphi(u)=w$とすると、$f(x,y,u)=x^w\ {\rm mod}\ u$である。

今回の場合は$w=a\uparrow\uparrow (n-1)\ {\rm mod}\ \varphi(u)$を求めれば良いので、再帰関数を利用すると良い。以下では、再帰の回数が$O(\log m)$で済むことを示す。

まず、$u\leq m$より、$\varphi(u)\leq u$であり、

• $u$が奇数の時、$u$の素因数分解を$\prod_{i=1}^k p_i^{e_i}$とする。（ただし、$p_1,p_2,\cdots p_k$は全て奇数）この時、$\varphi(u)=\prod_{i=1}^k p_i^{e_i-1}(p_i-1)$となるため、$\varphi(u)$は偶数となる。また、$\varphi(u)<u$である。
• $u$が偶数の時、$u$以下の偶数は全て$u$と互いに素でないので、$\varphi(u)\leq \frac{u}{2}$である。

以上より、どんな$u$についても$\varphi$を2回適用すると、その値は半分以下になる。よって、再帰の回数は$O(\log m)$で済む。（出典：アメリカ音ゲーマーぁぁさんのツイート）

また、この問題では$f(x,y,z)$を求める際、$z$の素因数分解がボトルネックとなるので、計算量は$2\left(\sqrt{m}+\sqrt{\frac{m}{2}}+\sqrt{\frac{m}{4}}+\cdots\right)=O(\sqrt{m})$以下となる。よって、制限時間内に間に合う。

解答例は以下の通り。

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378