Fast Power

Calculate the an % b where a, b and n are all 32bit non-negative integers.

Example

For 231 % 3 = 2

For 1001000 % 1000 = 0

Challenge

O(logn)

思想：recursion算一半，然后base case，处理算完一半以后的情况；

公式就是 (a*b) % p = (a%p * b%p) % p;

a^n % b = (a ^ n/2 % b * a ^ n/2 % b ) % b;

如果n为奇数，还要再加一个 (a%b *(a ^ n/2 % b * a ^ n/2 % b ) )% b;

public class Solution { /** * @param a: A 32bit integer * @param b: A 32bit integer * @param n: A 32bit integer * @return: An integer */ public int fastPower(int a, int b, int n) { if(a == 1 || n == 0) return 1 % b; if(n == 1) return a % b; long halfpower = fastPower(a, b, n/2) % b; halfpower = ((halfpower % b) * (halfpower % b)) % b; if(n % 2 == 0) { return (int)halfpower; } else { return (int)(((a % b) * halfpower) % b); } } }