蓝桥杯 adv204 快速幂

蓝桥杯 adv204 快速幂

问题描述

给定 A, B, P,求(A^B) mod P。

输入格式

输入共一行。

第一行有三个数,N, M, P。

输出格式

输出共一行,表示所求。

样例输入

2 5 3

样例输出

2

数据规模和约定

共10组数据

对100%的数据,A, B为long long范围内的非负整数,P为int内的非负整数。

参考解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>

using namespace std;

long long func(long long a, long long b, int p) {
// (a * b) % c = (a % c) * (b % c) % c
if (b == 0)
return 1;
if (b % 2 == 1)
return func(a, b-1, p) * (a % p) % p;
else { // 分奇偶递归减小,仍在 ll 的范围内
long long t = func(a, b/2, p);
return t * t % p;
}
}

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

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×