## 反复平方法

### 预处理

$O(k)$预处理出来以下的数：
$m ^ {2 ^ 0}$ $\bmod$ $p$
$m ^ {2 ^ 1}$ $\bmod$ $p$
$m ^ {2 ^ 2}$ $\bmod$ $p$

$m ^ {2 ^{\log{k}}}$ $\bmod$ $p$

### 算答案

$4^{2 ^ 2}$ $\bmod$ $10$ $=$ $6$
$4^{2 ^ 0}$ $\bmod$ $10$ $=$ $4$
$(6$ $\times$ $4)$ $\bmod$ $10$ $=$ $4$

$4^5$ $\bmod$ $10$ $=$ $1024$ $\bmod$ $10$ $=$ $4$

### 把两个步骤合在一起

 1 2 3 4 5 6 7 8 9  int qmi(int m, int k, int p) { int t = 1 % p; while (k) { if (k & 1) t = (LL)t * m % p; m = (LL)m * m % p; k >>= 1; } return t; } 

• k & 1 $k$ 的末位（二进制）为$0$
• LL 乘的过程可能会爆int，使用long long

## 应用题

### 幂次方

（输入输出不用管他）

#### 解法

qmi(X, N, 233333)