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

这个大佬$tql$！ [甩链接](https://www.luogu.org/problem/show?pid=U18990) 这个题首先我们可以发现，$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$的时间里，求出结果。 至于代码，先欠着吧（逃。 哦，还有，对于上面的定理，有个证明，但因为我菜啊，所以暂时看不太懂~~（其实就是同余那堆东西没好好学~~ [证明一](https://zhuanlan.zhihu.com/p/31510871) [证明二(我感觉这个比一更加海星)](https://zhuanlan.zhihu.com/p/30829973)