[hihoCoder]1777 彩球

原题

https://hihocoder.com/problemset/problem/1777

输入

第一行三个正整数 n, k, P
对于50%的数据,有1 ≤ n, k, P ≤ 10^9
对于100%的数据,有1 ≤ n, k, P ≤ 10^18

解法

考察大数的幂次取模
乘法溢出

用快速幂和快速乘解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>

using namespace std;

// 快速乘

long long fastMultiply(long long a, long long b, long long p) {

long long ans = 0;
long long t = a;

while (b) {
if (b & 1) {
ans = (ans + t) % p;
}
t = (t + t) % p;
b = b >> 1;
}

return ans;
}


// 快速幂
long long fastPow(long long n, long long k, long long p) {
long long ans = 1;
long long t = n;
while (k) {
if (k & 1) {
ans = fastMultiply(ans, t, p);
}
t = fastMultiply(t, t, p);
k = k >> 1;
}
return ans;
}



int main(int argc, char const *argv[]) {

long long n, k, p;
scanf("%lld%lld%lld", &n, &k, &p);

printf("%lld\n", fastPow(k, n, p));

return 0;
}