光速幂

黑科技……

使用情况

快速求 \(a^b \bmod m\) 的值。
在幂运算的底数和取余的模数已经确定的情况下可以使用光速幂。
比如 P3747 [六省联考 2017] 相逢是问候 中需要用光速幂，否则很难卡过。
\(\color{White}{\text{其实是因为那题才来学光速幂的}}\)

原理

根据拓展欧拉定理：

对于 \(a,m\in \mathbb{Z}\)，有 \(a^b \equiv \begin{cases}a^b&b< \varphi(m) \\a^{\left( b \bmod \varphi(m) \right)+\varphi(m)}&b>\varphi(m)\end{cases} \pmod{p}\)

可以先把 \(b\) 的值缩小到 \(2 \times \varphi(m)\)。
令 \(k=\left\lceil\sqrt{b}\,\right\rceil\)，对于 \(b\) 显然有 \(b = \left\lfloor\dfrac{b}{k}\right\rfloor \times k +b \bmod k\)
就可以将 \(a^b\) 转化为： $$a^b =a^{\left\lfloor\dfrac{b}{k}\right\rfloor \times k +b\bmod k}$$

写法

所以就能 \(O(sqrt(n))\) 地预处理：
定义两个数组 \(x,y\)
令 \(x_i=a^i,i \in \left[ 1,k \right]\)，显然可以通过 \(x_i=x_{i-1} \times a\) 得到数组 \(x\)，其中要初始化数组为 \(x_0=1,x_1=a\)。
令 \(y_i=\left( a^k \right)^i\)，显然可以通过 \(y_i=y{i-1}\times a^k (x_k)\) 得到数组 \(y\)，其中初始化数组为 \(y_0=1,y_1=x_k\)。
所以 \(a^b \bmod p = x_{\left\lfloor\dfrac{b}{k}\right\rfloor} \times y_{b \bmod k}\)。

代码

P1226 【模板】快速幂||取余运算
没用 \(\varphi\)

#include 
#define int long long
using namespace std;int rd(){
	int w=0,v=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')v=-1;c=getchar();}
	while(c>='0'&&c<='9'){w=(w<<1)+(w<<3)+(c&15);c=getchar();}return w*v;
}const int N=1e5+5;int a,b,p,bl,x[N],y[N];int gsm(int s){return s<=bl?x[b]:y[b/bl]*x[b-b/bl*bl]%p;}
signed main(){
	a=rd(),b=rd(),p=rd();bl=sqrt(b)+1;x[0]=y[0]=1%p;for(int i=1;i<=bl;i++)x[i]=x[i-1]*a%p;
	for(int i=1;i<=bl;i++)y[i]=y[i-1]*x[bl]%p;cout<