#CSPJ2022A. 乘方(pow)
乘方(pow)
乘方(pow)
版权信息: CCF-CSP-J2022
任务总览
任务名称 | 时间限制 | 内存限制 | 分数 |
---|---|---|---|
计算 a^b | 1 sec | 256 MB | 100 points |
题目描述
小文同学遇到了这样一个题:给定正整数 a
和 b
,求 a^b
的值。
a^b
表示 b 个 a 相乘的结果。- 例如
2^3 = 2 × 2 × 2 = 8
。
但是 **当计算结果超过 10^9
时,输出 -1
**,否则输出 a^b
的值。
输入格式
输入共 一行,包含两个正整数 a, b
。
输出格式
输出 一行,如果 a^b
的值不超过 10^9
,则输出该值,否则输出 -1
。
样例
输入 #1
10 9
输出 #1
1000000000
输入 #2
23333 66666
输出 #2
-1
数据范围
- 对于 10% 的数据,保证
b = 1
。 - 对于 30% 的数据,保证
b ≤ 2
。 - 对于 60% 的数据,保证
b ≤ 30
,且a^b ≤ 10^18
。 - 对于 100% 的数据,保证
1 ≤ a, b ≤ 10^9
。
题目分析
1. 指数计算的溢出
- 由于
a, b
最大可以达到10^9
,直接计算a^b
可能会爆掉。 - 因此不能使用
int
类型存储。
2. 计算优化
- 快速幂(Binary Exponentiation)
a^b = (a^(b/2)) × (a^(b/2))
,利用递归或者位运算减少计算量。- **时间复杂度 O(log b)**,比直接循环乘法 O(b) 更快。
- 模拟乘法,提前终止
- 逐步累乘
a
,如果 **中间结果超过10^9
**,就直接输出-1
并结束。
- 逐步累乘
时间复杂度分析
- 暴力法(直接循环
b
次)最坏情况 O(b) = O(10^9),不可行! - 快速幂法(Binary Exponentiation) O(log b),最坏情况 log(10^9) ≈ 30,可行!
- 模拟乘法(逐步累乘) O(b),但 一旦超过
10^9
就终止,最多执行 10 次(对于a = 10, b = 9
的情况),可行!