CH101 a ^ b （快速幂）

求 a 的 b 次方对 p 取模的值。

输入格式

三个整数 a,b,p ,在同一行用空格隔开。

输出格式

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

数据范围

0≤a,b,p≤109

输入样例：

3 2 7

输出样例：

2

同样地，对于每个b，我们可以表示为（整数b的二进制形式有k位）。
$b = c_02^0+c_12^1+c_22^2+....c_{k-2}2^{k-2}+c_{k-1}2^{k-1}$

即
$$ b = \sum_{i=0}^{k-1}c_i2^i $$

那么对于

$$ a^b =a^{\sum_{i=0}^{k-1}c_i2^i} $$

因为 $k$ = $\lceil log_2(b+1)\rceil$（向上取整，即对于整数b的二进制位数）

所以上述乘积项的项数不多于$\lceil log_2(b+1)\rceil$个，复杂度为$O(log_2 b)$。

而我们本质上要求的就是若干个$a^{2^i}$相乘的结果。

又因为

$a^{2^i} = (a^{2^{i-1}})^2$

那么我们只需要k次递推求出每次的乘积项，当$c_i$ = 1时，即二进制位为1的时候将乘积累积到答案中。我们可以用b & 1运算表示b的二进制下的最低位，并用b >> 1来舍去最低位。

int ans = 1;
    for (;b;b >>= 1){
        if (b & 1){
            ans = 1ll * ans * a;//通过乘上1ll进行类型转换
        }
        a = 1ll * a * a;
    }

而根据取模的性质

(a + b) % p = (a % p + b % p) % p （1）

(a - b) % p = (a % p - b % p) % p （2）

(a * b) % p = (a % p * b % p) % p （3）

a ^ b % p = ((a % p)^b) % p （4）

即(a * b)% p = (a % p * b % p ) % p

我们可以让 ans,a分别%p

#include <iostream>
using namespace std;

int main(){
    int a,b,p;
    cin >> a >> b >> p;
    int ans = 1 % p;
    for (;b;b >>= 1){
        if (b & 1){
            ans = 1ll * ans * a % p;
        }
        a = 1ll * a * a %p;
        cout << ans << " ";
    }
    cout << ans;
}