计蒜客41299 – super_log

题目链接:ICPC 2019 南京网络赛 B

题目要求

$$ a^{a^{a^{\cdots}}}  \pmod{m}$$

其中共有$b$个$a$。

考虑欧拉函数降幂。我们常用的欧拉函数降幂是这样的:

$$ a^b \equiv \left\{ \begin{aligned} & a^{b \bmod \varphi(m)} & {\rm gcd}(a, m)=1 \\ & a^b &{\rm gcd}(a, m)\neq 1, b < \varphi(m) \\ & a^{b \bmod\varphi(m) +\varphi(m)} &{\rm gcd}(a, m)\neq 1, b \geq \varphi(m)  \end{aligned} \right . \pmod{m} $$

其中第一个式子是被包含在后两个式子当中的。那么对于我们要求的式子,记$f(a,b,m)$为$b$个$a$在这种形式下对$m$取模的值,记$t(a,b)$为$b$个$a$在这种形式下的值。我们可以得这样的递推关系,当$t(a,b) < \varphi(m)$时,我们可以直接递归求$t(a,b)$,否则$f(a,b,m) = a^{f(a,b-1,\varphi(m)) + \varphi(m)} \pmod{m}$。在判断$t(a,b)$和$\varphi(m)$的时候,由于$t(a,b)$增长的速度很快,对于$a \geq 3$,只要$b \geq 2$,一定满足$t(a,b) \geq m$,其他情况特判即可。由于不断的对$m$取$\varphi(m)$,所以第三个参数会很快收敛到$1$,所以跑得很快。

 

说点什么

avatar
50
  Subscribe  
提醒