AcWing 875. 快速幂

题目

给定 $n$ 组 $a_i,b_i,p_i$，对于每组数据，求出 ${a_i}^{b_i}mod{p_i}$ 的值。

输入格式 第一行包含整数 $n$。

接下来 $n$ 行，每行包含三个整数 $a_i,b_i,p_i$。

输出格式 对于每组数据，输出一个结果，表示 ${a_i}^{b_i}mod{p_i}$ 的值。

每个结果占一行。

数据范围 $1≤n≤100000,1≤a_i,b_i,p_i≤2×10^9$ 输入样例：

2
3 2 5
4 3 9

输出样例：

4
1

思路

主要思路是将 $b$ 转换成二进制，将二进制中位为 $1$ 的初始化，最终结果由预处理的数值拼凑而成。

代码

#include <iostream>

using namespace std;

typedef long long LL;

// 快速幂代码
int fast_power(int a, int b, int p)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        
        b >>= 1;
        a = (LL)a * a % p;
    }
    
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    while (n -- )
    {
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        
        printf("%lld\n", fast_power(a, b, p));
    }
    
    return 0;
}