题目描述
小文同学刚刚接触了信息学竞赛,有一天她遇到了这样一个题:给定正整数 $a$ 和 $b$,求 $a^b$ 的值是多少。
$a^b$ 即 $b$ 个 $a$ 相乘的值,例如 $2^3$ 即为 $3$ 个 $2$ 相乘,结果为 $2×2×2=8$。
“简单!”小文心想,同时很快就写出了一份程序,可是测试时却出现了错误。
小文很快意识到,她的程序里的变量都是 int
类型的。
在大多数机器上,int
类型能表示的最大数为 $2^31−1$,因此只要计算结果超过这个数,她的程序就会出现错误。
由于小文刚刚学会编程,她担心使用 int
计算会出现问题。
因此她希望你在 $a^b$ 的值超过 $10^9$ 时,输出一个 $-1$ 进行警示,否则就输出正确的 $a^b$ 的值。
然而小文还是不知道怎么实现这份程序,因此她想请你帮忙。
输入格式
输入共一行,两个正整数 $a,b$。
输出格式
输出共一行,如果 $a^b$ 的值不超过 $10^9$,则输出 $a^b$ 的值,否则输出 $-1$。
数据范围
对于 $10%$ 的数据,保证 $b=1$。
对于 $30%$ 的数据,保证 $b≤2$。
对于 $60%$ 的数据,保证 $b≤30,a^b≤10^18$。
对于 $100%$ 的数据,保证 $1≤a,b≤10^9$。
输入样例1:
10 9
输出样例1:
1000000000
输入样例2:
23333 66666
输出样例2:
‐1
算法1
(快速幂) $O(logn)$
快速幂……大家都知道吧
C++ 代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int cnt = 1e+9;
int a, b;
int power(int x, int y) {
int s = 1;
while (y) {
if (y & 1)
s *= x;
if (s > cnt || x > cnt)
return -1;
x *= x;
y >>= 1;
}
return s;
}
signed main() {
// freopen("pow.in", "r", stdin);
// freopen("pow.out", "w", stdout);
cin >> a >> b;
cout << power(a, b) << endl;
return 0;
}
算法2
(特判)
反正就是……这个……学过对数的都应该知道吧
#include <bits/stdc++.h>
using namespace std;
long long a, b, ans;
int main(){
cin >> a >> b;
if (b * log10(a) > 9)
ans = -1;
else
ans = pow(a, b);
cout << ans << endl;
return 0;
}
6 %%%大佬 第二种方法真想不到