Exponents
Exponents
Time limit: 1 s.
Memory limit: 256 MB
Given 3 integers \(A\), \(B\) and \(M\). Compute: \(A ^ B \mod M\)
Input
The input consists of \(3\) integers \(A\), \(B\) and \(M\). \((0 \le A, B \le 10^6), (1 \le M \le 10^9)\)
Output
Output the value of \(A ^ B \mod M\)
Scoring
| Group | Constraints | Points |
|---|---|---|
| \(1\) | \(A \equiv 0 \pmod{M}\) | \(13\) |
| \(2\) | \(A \equiv 1 \pmod{M}\) | \(11\) |
| \(3\) | \(A \equiv M-1 \pmod{M}\) | \(35\) |
| \(4\) | — | \(41\) |
Examples
Input
2 3 10
Output
8
Input
10 3 5
Output
0
Input
7 100 6
Output
1
Solution
Use binary exponentiation. While \(B>0\), square the base at every step. If the current bit of \(B\) is \(1\), multiply it into the answer. All values are reduced modulo \(M\) immediately.
This takes \(O(\log B)\) time and \(O(1)\) memory.
#include <iostream>
using namespace std;
int main() {
long long a, b, m;
cin >> a >> b >> m;
a %= m;
long long answer = 1 % m;
while (b > 0) {
if (b % 2 == 1) {
answer = answer * a % m;
}
a = a * a % m;
b /= 2;
}
cout << answer << '\n';
}