U18990超速幂【据说是接近提高难度的】

· · 个人记录

这个大佬tql！

甩链接

这个题首先我们可以发现，k<=10^{50000000},那如果我们是普通的快速幂的话，刨除常数不讲，大约是log_210^{50000000},那么我们可以对这个东西换个底，就是log_210^{50000000}=\frac{lg10^{50000000}}{lg2}

作为一个个刚刚考完了对数函数的蒟蒻，我可以负责任地告诉你lg2=0.3010

啊，大约也就是1e8的数据吧！看起来不能水了qnq.

那么据\color{purple}rqy \color{fuchsia}rqy \color{violet}rqy \color{pink}rqy \color{thistle}rqy \color{Cadetblue}rqy(皮一下) 说,这个有这么一个公式：

n^k\equiv \begin{matrix} \qquad\ n^{[k\ \ mod \ \ \phi(m)]+\phi(m)} \ \ (k>=\phi(m))\\n^k \qquad\ (k<\phi(m)) \end{matrix} \qquad\ (mod \ \ m)

那么事实上，我们会发现，无论如何，在经历过我们的一系列操作后,k会变小,所以之后我们就可以在log的时间里，求出结果。

至于代码，先欠着吧（逃。

哦，还有，对于上面的定理，有个证明，但因为我菜啊，所以暂时看不太懂（其实就是同余那堆东西没好好学

证明一

证明二(我感觉这个比一更加海星)