java 描述 给出一个整数a和一个正整数n,求乘方an。 输入 一行,包含两个整数a和n。-1000000 <= a <= 1000000,1 <= n <= 10000。 输出 一个整数,即乘方结果。题目保证最终结果的绝对值不超过1000000。
时间: 2024-01-24 14:17:21 浏览: 26
可以使用快速幂算法来解决这个问题。首先考虑暴力求解,将a连乘n次,时间复杂度是O(n)的,不够高效。快速幂算法是利用指数的二进制拆分,将指数n表示成二进制形式,例如十进制数13表示成二进制数1101,那么a^13 = a^(2^3) * a^(2^2) * a^(2^0)。每次将指数n的二进制形式中的一位转化为对应的幂后相乘,可以将时间复杂度降到O(logn)。
Java代码实现如下:
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
int n = scanner.nextInt();
long result = quickPower(a, n);
System.out.println(result);
}
// 快速幂算法
private static long quickPower(int a, int n) {
long result = 1L;
long base = a;
while (n != 0) {
if ((n & 1) != 0) {
result *= base;
}
base *= base;
n >>= 1;
}
return result;
}
}
```
注意在计算过程中要使用long类型,避免结果溢出。