首页 > 代码库 > Lintcode: Fast Power 解题报告

Lintcode: Fast Power 解题报告

2024-08-08 23:54:56   211人阅读

Fast Power

原题链接：http://lintcode.com/en/problem/fast-power/#

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

Example

For 231 % 3 = 2

For 1001000 % 1000 = 0

Challenge

O(logn)

Tags Expand

技术分享

SOLUTION 1:

实际上这题应该是suppose n > 0的。

我们利用 取模运算的乘法法则： http://baike.baidu.com/view/4887065.htm

(a * b) % p = (a % p * b % p) % p （3）

将 a^n % b 分解为 (a^(n/2) * a^(n/2) * (a)) %b = ((a^(n/2) * a^(n/2))%b * (a)%b) %b = ((a^(n/2)%b * a^(n/2)%b)%b * (a)%b) %b

实现如下：

注意2个base case: n = 0 n = 1都要特别处理。因为n = 1时，会分解出一个pow(a, b, 1)，这个会不断循环调用。

技术分享
 1 class Solution { 2     /* 3      * @param a, b, n: 32bit integers 4      * @return: An integer 5      */ 6     /* 7      * @param a, b, n: 32bit integers 8      * @return: An integer 9      */10     public static int fastPower(int a, int b, int n) {11         // write your code here12         long ret = pow(a, b, n);13         14         return (int) ret;15     }16     17     // suppose n > 018     public static long pow(int a, int b, int n) {19         if (a == 0) {20             return 0;21         }22         23         // The base case.24         if (n == 0) {25             return 1 % b;26         }27         28         if (n == 1) {29             return a % b;30         }31         32         long ret = 0;33         34         // (a * b) % p = (a % p * b % p) % p （3）35         ret = pow(a, b, n / 2);36         ret *= ret;37         38         // 这一步是为了防止溢出39         ret %= b;40         41         if (n % 2 == 1) {42             ret *= pow(a, b, 1);43         }44         45         // 执行取余操作46         ret = ret % b;47         48         return ret;49     }50 };
View Code

SOLUTION 2:

或者你也可以把pow(a, b, 1)直接写为a % b. 以下解法把base case: n = 1就拿掉了。

技术分享
 1 // SOLUTION 2: 2     // suppose n > 0 3     public static long pow(int a, int b, int n) { 4         if (a == 0) { 5             return 0; 6         } 7          8         // The base case. 9         if (n == 0) {10             return 1 % b;11         }12         13         long ret = 0;14         15         // (a * b) % p = (a % p * b % p) % p （3）16         ret = pow(a, b, n / 2);17         ret *= ret;18         19         // 这一步是为了防止溢出20         ret %= b;21         22         if (n % 2 == 1) {23             ret *= (a % b);24         }25         26         // 执行取余操作27         ret = ret % b;28         29         return ret;30     }
View Code

 

GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/lintcode/math/FastPower.java

Lintcode: Fast Power 解题报告


联系
我们