【板刷算进计划】a^b

快速幂模板题。

容易发现，$a^b$ 这个算式，当 $b$ 是偶数的时候，$a^b={a^{b/2}}^2$，只需要求解 $a^{b/2}$ 即可。

如果 $b$ 是奇数，那么 $a^b = ${a^{b/2}}^2\times a$，特殊处理一下即可。

边界条件：$b=0\to 1$。

如果模数为 $1$ 需要特判，答案永远为 $0$。

时间复杂度 $O(\log b)$。

#include 
#define int long long

using namespace std;

int ksm(int a, int b, int c)
{
  if (!b)
    return 1 % c;
  int ans = ksm(a, b >> 1, c);
  ans = ans * ans % c;
  if (b & 1)
    ans = ans * a % c;
  return ans;
}

signed main()
{
  int a, b, p;
  cin >> a >> b >> p;
  cout << ksm(a, b, p) << '\n';
  return 0;
}

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