欧拉降幂

公式

$n^x \% m = n^{x \% \phi(m) + \phi(m)} \quad \% \quad m \quad (x > \phi(m))$

迭代的次数不会超过$log(n)$次.

由于$x \geq \phi(m)$, 当$x < \phi(m)$时直接暴力算就可以.

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#define Mod(x,p) x < p ? x : x % p + p;     // 统一用这种取模
bool vis[maxn];
int prime[maxn], phi[maxn];
void init() { // 线性筛预处理欧拉函数
clr(vis, 0);
phi[1] = 1;
int tot = 0;
for (int i = 2; i < maxn; i++) {
if (!vis[i]) {
prime[tot++] = i;
phi[i] = i - 1;
}
for (int k = 0; k < tot && 1LL * i * prime[k] < maxn; k++) {
vis[i * prime[k]] = 1;
if (i % prime[k] == 0) {
phi[i * prime[k]] = phi[i] * prime[k];
break;
}
phi[i * prime[k]] = phi[i] * (prime[k] - 1);
}
}
}

ll my_pow(ll a,ll b,ll mod){
ll ret = 1;
while(b){
if(b & 1) ret = Mod(ret * a,mod);
a = Mod(a * a,mod);
b >>= 1;
}
return Mod(ret,mod);
}

ll solve(ll base, ll n, int mod){

}
Thank you for your support!