Fast Power

本文主要是介绍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);}}
}

 

这篇关于Fast Power的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---