欧拉降幂公式
a
b
≡
a^b\equiv
ab≡
a
b
%
ϕ
(
p
)
a^{b \% \phi(p)}
ab%ϕ(p)
(
m
o
d
(mod
(mod
p
)
p)
p)
a
b
a^{b}
ab
(
m
o
d
(mod
(mod
p
)
p)
p)
(
m
o
d
(mod
(mod
p
)
p)
p)
b
<
ϕ
(
p
)
b<\phi(p)
b<ϕ(p)
a
b
%
ϕ
(
p
)
+
ϕ
(
p
)
a^{b \% \phi(p)+\phi(p)}
ab%ϕ(p)+ϕ(p)
(
m
o
d
(mod
(mod
p
)
p)
p)
b
≥
ϕ
(
p
)
b\ge\phi(p)
b≥ϕ(p)
求解代码：
LL euler_phi(LL n) {//求解欧拉函数
LL k = (LL)sqrt(n + 0.5);
LL ans = n;
for (int i = 2; i <= k; i++) {
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
