快速幂--a^b%p

题目描述

求 $a$ 的 $b$ 次方对 $p$ 取模的值。 输入格式 三个整数 $a,b,p$ ,在同一行用空格隔开。 输出格式 输出一个整数，表示​​a^b mod p​​的值。 数据范围

$​0≤a,b≤10^9$ $​1≤p≤10^9$ 输入样例：

3 2 7

输出样例：

2

思路

对于C++，直接求 $a ^ b % p$ 会超过存储最大值，所以可以用反复平方法/快速幂方式计算。 $a^b$ 将 $b$ 表示成二进制，不妨设 $b=11010$

我们先预处理求出： $a^{2^0} = a$ $a^{2^1} = ({a^{2^0}})^2$ $以此类推...$

之后我们可以将 $a^b$ 拆分成 $a^{2^0} * a^{2^1} * a^{2^3} * a^{2^4}$, 其中每个值我们都可以从预处理中获取

代码

#include <iostream>

using namespace std;

typedef long long LL;

int fast_power(int a, int b, int p)
{
    int res = 1 % p;
    while (b)
    {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    
    return res;
}

int main()
{
    int a, b, p;
    cin >> a >> b >> p;
    cout << fast_power(a, b, p) << endl;
    
    return 0;
}