# Fast Power

## 题解

(a * b) % p = ((a % p) * (b % p)) % p


$a^n = a^{n/2} \cdot a^{n/2} = a^{n/4} \cdot a^{n/4} \cdot a^{n/4} \cdot a^{n/4} \cdot = ...$

### Python

class Solution:
"""
@param a, b, n: 32bit integers
@return: An integer
"""
def fastPower(self, a, b, n):
if n == 1:
return a % b
elif n == 0:
# do not use 1 instead 1 % b because b = 1
return 1 % b
elif n < 0:
return -1

# (a * b) % p = ((a % p) * (b % p)) % p
product = self.fastPower(a, b, n / 2)
product = (product * product) % b
if n % 2 == 1:
product = (product * a) % b

return product


### C++

class Solution {
public:
/*
* @param a, b, n: 32bit integers
* @return: An integer
*/
int fastPower(int a, int b, int n) {
if (1 == n) {
return a % b;
} else if (0 == n) {
// do not use 1 instead (1 % b)! b = 1
return 1 % b;
} else if (0 > n) {
return -1;
}

// (a * b) % p = ((a % p) * (b % p)) % p
// use long long to prevent overflow
long long product = fastPower(a, b, n / 2);
product = (product * product) % b;
if (1 == n % 2) {
product = (product * a) % b;
}

// cast long long to int
return (int) product;
}
};


### Java

class Solution {
/*
* @param a, b, n: 32bit integers
* @return: An integer
*/
public int fastPower(int a, int b, int n) {
if (n == 1) {
return a % b;
} else if (n == 0) {
return 1 % b;
} else if (n < 0) {
return -1;
}

// (a * b) % p = ((a % p) * (b % p)) % p
// use long to prevent overflow
long product = fastPower(a, b, n / 2);
product = (product * product) % b;
if (n % 2 == 1) {
product = (product * a) % b;
}

// cast long to int
return (int) product;
}
};