关于求平方的两道题

题目：实现pow(x, n)函数

题目来源：LeetCode--50. Pow(x, n)

原题目：

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10 Output: 1024.00000

Example 2:

Input: 2.10000, 3 Output: 9.26100

Example 3:

Input: 2.00000, -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

-100.0 < x < 100.0n is a 32-bit signed integer, within the range [−2^31, 2^31 − 1]

这道题还是比较直观的，一种解法是使用循环，但是并不是最好的。我们可以使用类似二分的思想，比如：x^16 = x^8 * x^8，所以我们只需要计算到x^8即可，对于x^8也是如此我们只需要计算到x^4即可。

下面看AC代码：

public double myPow(double x, long n) { if (n < 0) { x = 1 / x; n = -n; } return pow(x, n); } private double pow(double x, long n) { if (n == 0) { return 1; } return (n & 1) == 0 ? pow(x * x, n >> 1) : x * pow(x * x, n >> 1); }

---

LeetCode--372. Super Pow

原题目：

Your task is to calculate a^b mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example 1:

Input: a = 2, b = [3] Output: 8

Example 2:

Input: a = 2, b = [1,0] Output: 1024

计算a^b次方对1337取模后的结果，由于b可能很大，使用数组的形式给出。

AC代码：

public int superPow(int a, int[] b) { if(b == null || b.length == 0) { return 1; } return superPowhelp(a, b, b.length - 1); } private int superPowhelp(int a, int[] b, int cur) { if (cur == -1) { return 1; } return pow(superPowhelp(a, b, cur - 1), 10) * pow(a, b[cur]) % 1337; } private int pow(int a, int b) { if (b == 0) { return 1; } a %= 1337; return (b & 1) == 0 ? pow(a * a, b >> 1) % 1337 : a * pow(a * a, b >> 1) % 1337; }

好了，我们下期见！！