我们先回忆一下快速幂是怎么解决的 我们是利用二进制的性质将复杂度优化到单词询问
O
(
log
i
n
d
e
x
)
O(\log index)
O(logindex) 但是在有些题目中，可能复杂度不支持我们再在原有复杂度上增加一个
log
\log
log（比如询问变成
1
0
7
10^7
107次） 那么这个时候就需要运用到光速幂的内容了
当我们计算
a
b
m
o
d
p
a^b \bmod p
abmodp的时候，我们可以令
b
=
k
s
+
t
b=ks+t
b=ks+t，其中
s
,
t
s,t
s,t是常数，
t
≤
s
t\leq s
t≤s 那么我们只需要预处理出任意一个
a
0
,
a
1
,
a
2
.
.
.
a
s
a^0,a^1,a^2...a^s
a0,a1,a2...as，
a
0
,
a
s
,
a
2
s
,
a
3
s
.
.
.
a
⌈
p
s
⌉
s
a^0,a^s,a^{2s},a^{3s}...a^{\lceil\frac{p}{s}\rceil s}
a0,as,a2s,a3s...a⌈sp⌉s，那么最后询问答案就是
a
k
s
×
b
t
a^{ks}\times b^t
aks×bt就可以
O
(
1
)
O(1)
O(1)得到答案 那为什么我们的预处理的上界要取到
p
p
p呢？其实应该上界是
ϕ
(
p
)
\phi(p)
ϕ(p)，但是为了方便我们就算到
p
p
p。 根据欧拉定理
a
ϕ
(
p
)
≡
1
m
o
d
p
a
b
≡
a
b
m
o
d
ϕ
(
p
)
m
o
d
p
\begin{aligned} a^{\phi(p)}&\equiv 1\ &\bmod p \\ a^{b}&\equiv a^{b \bmod \phi(p)}\ &\bmod p \end{aligned}
aϕ(p)ab≡1≡abmodϕ(p)modpmodp 也就是说，对于任意的
a
b
a^b
ab，一定有一个
a
c
(
c
≤
ϕ
(
p
)
)
a^c(c\leq\phi(p))
ac(c≤ϕ(p))和他模
p
p
p同余
那么显然当
s
s
s取
⌈
p
⌉
\lceil\sqrt p\rceil
⌈p⌉时可以做到不漏的情况下复杂度最优
那么我们直接处理出这些幂就可以了
下面给出的是洛谷模板题代码，记得指数要
m
o
d
ϕ
(
p
)
\bmod\ \phi(p)
modϕ(p)
