AcWing - 快速幂(快速幂)

题目链接:https://www.acwing.com/problem/content/description/877/
时/空限制：1.500000s / 64MB

题目描述

给定n组ai,bi,pi，对于每组数据，求出abiimod pi的值。

输入格式

第一行包含整数n。

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

输出格式

对于每组数据，输出一个结果，表示abiimod pi的值。

每个结果占一行。

数据范围

1≤n≤100000,
1≤ai,bi,pi≤2∗10^9

输入样例

2
3 2 5
4 3 9

输出样例

4
1

解题思路

题意:求出a^b mod p 的值。
思路:直接上快速幂的模板就完事了，注意乘的时候要转化为long long型的，直接定义成long long也可以。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int Fast_Power(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = 1ll * res * a % p;//转化为long long型
        a = 1ll * a * a % p;
        b >>= 1;
    }
    return res;
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        printf("%d\n", Fast_Power(a, b, p));
    }
    return 0;
}