AcWing875. 快速幂

题目描述

给定 n 组 ai,bi,pi，对于每组数据，求出 ai的bi次方和pi取模的值。

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

接下来 n 行，每行包含三个整数 ai,bi,pi。

输出格式
对于每组数据，输出一个结果，表示 abiimodpi 的值。

每个结果占一行。

数据范围
1≤n≤100000,
1≤ai,bi,pi≤2×109
blablabla

输入样例

2
3 2 5
4 3 9

输出样例

4
1

---

算法

(快速幂解法) O ( n ∗ l o g b ) O(n∗logb) O(n∗logb)

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;


LL qmi(int a, int b, int p)
{
    LL res = 1 % p;//res存储结果
    while (b)  //对b进行二进制优化，从低位到高位
    {
        if (b & 1) res = res * a % p; //判断二进制最后一位是否为1 为1则乘上当前的a;
        a = a * (LL)a % p;// 更新一下 下一位对应的a 每一项是前一项的平方
        b >>= 1;// 右移一位 删除最后一位
    }
    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", qmi(a, b, p));
    }

    return 0;
}

---