@[紫钦](/space/show?uid=37839)
底数是 $1$ 时求出的值也是 $1$ ，没有溢出。
底数大于 $1$ 时，有 $2^{\phi(x)}\ge x$ ，所以如果已经溢出了之后也一定溢出了。
by hsfzLZH1 @ 2019-07-04 13:46:30
@[紫钦](/space/show?uid=37839) 您好，这么做是没有问题的。
by NaCly_Fish @ 2019-07-04 14:45:17
@[hsfzLZH1](/space/show?uid=43486) 你这个其实有问题，2^phi(6)=4<6
by 142857cs @ 2019-07-04 14:49:05
另外这个是在做快速幂的时候就判断好的
by NaCly_Fish @ 2019-07-04 14:49:19
不过mod 6意义下无法区分4和10（以及这个问题导致mod 18意义下无法区分16和34）是小问题，不影响结果
by 142857cs @ 2019-07-04 14:51:25
@[NaCly_Fish](/space/show?uid=115864) 可是您的快速幂中指数 $t$ （即 $res.rs$ ）本身是模过 $\phi(p)$ 的呀。如果 $a^{t\mod\phi(p)}<p$ ，不一定 $a^t<p$ 呀，可是您的 $res.rs$ 是递归的返回值，并不是原乘方塔了呀。
我是这么想的。。。我也不知道我的想法到底哪里有问题。。。
by 紫钦 @ 2019-07-04 16:51:23
@[hsfzLZH1](/space/show?uid=43486) 没太明白这个“溢出”的意思。。。
可能我太弱了。。。
喵喵喵~
by 紫钦 @ 2019-07-04 16:53:18
@[紫钦](/space/show?uid=37839)
扩展欧拉定理 $a^{b}~mod~p=a^{b~mod~\varphi(p)+\varphi(p)}~mod~p$ 。
溢出指符合使用条件， $b\ge \varphi(p)$ 。
by hsfzLZH1 @ 2019-07-04 16:58:00
@[hsfzLZH1](/space/show?uid=43486) 啊，这样子啊。
那确实，如果 $a^{t\mod\phi(p)}\geqslant p$ 一定有 $a^{t}\geqslant p$ ；
但问题是，如果 $a^{t\mod\phi(p)}< p$ 一定有 $a^{t}<p$ 吗？
感觉模完没溢出，原数不一定没溢出。
比如说，
$2^{2^{2^{2}}}\mod 7=2^{2^{2^{2}}mod \ 6+6?}\mod 7$ ，式子里的 $?$ 表示暂时不确定是否加上 $6$ ，
然后计算 $2^{2^{2}}\mod 6$ 并判断 $2^{2^{2}}$ 与 $6$ 的大小，
就需要计算 $2^2\mod 2$ 并判断 $2^2$ 与 $2$ 的大小，
递归计算 $2\mod 1$ 并判断 $2$ 与 $1$ 的大小，此时显然 $2>1$ ，于是加 $1$ ,
变成 $2^{2\mod 1+1}\mod 2=2\mod 2$ ，
发现 $2\geqslant 2$ ，于是加 $2$ ，
变成 $2^{2\mod 2+2}\mod 6=4\mod 6$ ，发现 $4<6$ ，于是不加 $6$ 。
到这里我觉得出问题了。。。因为显然那个 $6$ 是要加的，不过恰好 $2^6\equiv1\pmod7$ 。。。
是不是我没理解明白题解？
懵逼$ing$。。。
by 紫钦 @ 2019-07-04 17:27:46
@[紫钦](/space/show?uid=37839) 要找到模完没溢出，原数溢出的例子，假设模数是 $p$ ，原数是 $a^b\ge p$ （$b$ 可以是幂塔），模完后是 $a^{b~mod~\varphi(p)+\varphi(p)}<p$ 。设 $0\le k<\varphi (p)$ ， 一定有 $a^{\varphi(p)+k}<p$ ， $a=1$ 时的情况我们特殊讨论， $a$ 的值最小为 $2$ ， $2^{\varphi(p)+k}<p$ ，当且仅当 $p=6,\varphi(p)=2,k=0$ ，此时模完后的值是 $a^b~mod~p=4$ 。满足 $\varphi(x)=p=6$ 的数有 $7,9,14,18$ ，对于这些数，**（暂时还未确定）** 验证均有 $a^4~mod~p=a^{10}~mod~p$ ，则原方法无锅。否则可以构造出 hack 数据。
by hsfzLZH1 @ 2019-07-04 20:44:35