a^b

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

求 a 的 b 次方对 p 取模的值，其中 0≤a,b,p≤10^9
​

输入描述:

三个用空格隔开的整数a,b和p。

输出描述:

一个整数，表示a^b mod p的值。

示例1

输入

2 3 9

输出

8

解题思路：

首先看这题是让我们求a的b次方并对结果去余，如果是按照循环去做的话那么肯定时间复杂度O(b)太大了（b最大到1e+9），所以这里就要想办法把时间缩少，既然一个个循环着相乘不行，我们是否可以一次乘多个呢，这里就用到了快速幂的做法了。

时间复杂度：

O（logb）

快速幂知识点：

基于二分的思想，假如b是奇数的时候，那么就有a^b=a*a^b-1,这个时候b-1就是偶数了，假如是偶数的话就是a^b=a^b/2 * a^b/2, 举个例子吧，假如是
2^10 = 2^5 * 2^5;
2^5 = 2 * 2^4;
2^4 = 2^2 * 2^2;
2^2 = 2^1 * 2^1;
2^1 = 2 * 2^0;
所以有些时候偶数的情况就只需要乘它本身就够了，时间复杂度自然少了很多，这样的话2^10只需要5步就可以求出来了，但是循环的话，却需要十次。
在二进制中假如是2^10那么10对应的二进制就是1010，那么1号位，3号位都是1，所以就有了10 = 2^3+2^1=8+2,所以2^10=2^8+2^2。
所以二进制就先初始化ans = 1，用来存放累积的结果，然后判断b的二进制吗末尾是否为一来判断是奇数还是偶数，如果是奇数就乘以a，然后让a平方，并且b右移一位。只要b等于0，就返回ans。

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll QuickPow(ll a, ll b, ll mod) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans % mod;
}
int main() {
    ll a, b, p;
    scanf("%lld %lld %lld", &a, &b, &p);
    printf("%lld\n", QuickPow(a, b, p));
    return 0;
}