2023.3.10

这几天讲的倍增捏（一开始以优化 dp 为主，现在几乎纯倍增，6）。然后发现我不会快速幂。

Luogu P1226.【模板】快速幂||取余运算 传送门

我们知道任意整数可以表示成若干个 2 的次幂项的和。现在要求一个数的幂，那么我们可以将所需要求的幂转化为 2 的次幂项之和，即转化为二进制来计算。每次判断这个位置的二进制是 1 还是 0，进行相应的乘法计算。数学不好，直观的看一眼时间复杂度效率的差异：暴力做法是 log(n) 的，快速幂算法是 log₂n 的，速度一下快了很多。

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 ll ans = 1;
 5 ll a, b, p;
 6 ll aa, bb, mod;
 7 int main()
 8 {
 9     scanf("%lld%lld%lld", &a, &b, &p);
10     aa = a;
11     bb = b;
12     mod = p;
13     while(b)
14     {
15         if(b % 2) ans = ans * a % p;
16         a = a * a % p;
17         b /= 2;
18     }
19     printf("%lld", ans % p);
20     return 0;
21 }

最后记得输出之前再取模一次，一开始被你校 oj 上的数据卡住了：123456789 0 1。（多组数据别忘了清空，不开 long long 见祖宗。）