# Fast Power

{% tabs %}
{% tab title="Java" %}
```java
class Solution {
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        long ans = 1 % b, tmp = a;
        while(n > 0) {
            if (n % 2 == 1) {
                ans = ans * tmp % b;
            }
            tmp = tmp * tmp % b;
            n = n / 2;
        }
        return (int)ans;
    }
}

```
{% endtab %}

{% tab title="Python" %}
```python
class Solution:
    """
    @param a: A 32bit integer
    @param b: A 32bit integer
    @param n: A 32bit integer
    @return: An integer
    """
    def fastPower(self, a, b, n):
        # write your code here
        if n == 0:
            return 1 % b
        if n % 2 == 0:
            tmp = self.fastPower(a, b, n / 2)
            return tmp * tmp % b
        else:
            tmp = self.fastPower(a, b, n / 2)
            return tmp * tmp * a % b
```
{% endtab %}
{% endtabs %}

![](https://2784211123-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M-ELB26IpzCEJWSDi0m%2F-M-ELbsic2B8wwsarT-C%2F-M-EMqc6UhBUlpM3zyHy%2F1580805867266.jpg?alt=media\&token=11a20b67-9e32-4c02-bf02-c405dac8ef0f)
