# # 倍增

## # 快速幂

### # 递归求解

x^y=\left\{\begin{aligned} &1 & y=0 \\ &(x^{\frac{y}{2}})^2 & y\text{为大于0的偶数} \\ &(x^{\frac{y-1}{2}})^2\cdot x & y\text{为大于0的奇数}\end{aligned}\right.

#include <iostream>

using namespace std;
int fexp(int b, int p, int k) {
if (p == 0)
return 1 % k;
int half = fexp(b, p / 2, k);
int ans = (long long)half * half % k;
if (p & 1)
ans = (long long)ans * b % k;
return ans;
}

int main() {
int b, p, k;
cin >> b >> p >> k;
cout << b << "^" << p << " mod " << k << "=" << fexp(b, p, k);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

### # 迭代求解

#include <iostream>

using namespace std;

int fexp(int b, int p, int k) {
int ans = 1 % k;
while (p) {
if (p & 1)
ans = (long long)ans * b % k;
b = (long long)b * b % k;
p >>= 1;
}
return ans % k;
}

int main() {
int b, p, k;
cin >> b >> p >> k;
cout << b << "^" << p << " mod " << k << "=" << fexp(b, p, k);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

## # 练习题

### #ARC060E - Tak and Hotels (opens new window)

use proconio::input;

const K: usize = 18;

fn main() {
input! {
n: usize,
x: [usize; n],
l: usize,
q: usize,
queries: [(usize, usize); q],
}

let mut right = vec![vec![n; K]; n + 1];
for i in 1..=n {
let mut lo = i;
let mut hi = n;
while lo <= hi {
let mid = (lo + hi) >> 1;
let dist = x[mid - 1] - x[i - 1];
if dist > l {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
right[i][0] = hi;
}
for k in 1..K {
for i in 1..=n {
if right[i][k - 1] < n {
right[i][k] = right[right[i][k - 1]][k - 1];
}
}
}

let mut left = vec![vec![1usize; K]; n + 1];
for i in 1..=n {
let mut lo = 1usize;
let mut hi = i;
while lo <= hi {
let mid = (lo + hi) >> 1;
let dist = x[i - 1] - x[mid - 1];
if dist > l {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
left[i][0] = lo;
}
for k in 1..K {
for i in 1..=n {
if left[i][k - 1] > 1 {
left[i][k] = left[left[i][k - 1]][k - 1];
}
}
}

for (a, b) in queries {
let mut acc = 0;
let mut pos = a;
if a < b {
for k in (0..K).rev() {
if right[pos][k] < b {
acc ^= 1 << k;
pos = right[pos][k];
}
}
if pos != b {
acc += 1;
}
} else {
for k in (0..K).rev() {
if left[pos][k] > b {
acc ^= 1 << k;
pos = left[pos][k];
}
}
if pos != b {
acc += 1;
}
}
println!("{}", acc);
}
}

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86