[CSP-J 2022] 乘方

知识点

整数运算、溢出判断

解题思路

当a=1时答案恒为1，直接返回。否则循环乘a，每次先检查当前结果是否大于10^9/a，若是则下一步一定超限；否则安全相乘。a至少为2，至多约30次乘法就会完成或超限。

正确性说明

对正数，result*a>10^9等价于result>floor(10^9/a)，因此检查准确且乘法前不溢出。a>=2时乘积严格增大，超限后不可能重新回到范围内，提前输出-1正确。

易错点

等于10^9仍要输出；a=1且b=10^9必须直接返回；不要先做可能溢出的乘法再比较；不使用浮点pow判断边界。

复杂度

a=1时O(1)，否则O(min(b,log_a(10^9)+1))；额外空间O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){long long a,b;cin>>a>>b;if(a==1){cout<<1<<'\n';return 0;}long long ans=1;for(long long i=0;i<b;++i){if(ans>1000000000LL/a){cout<<-1<<'\n';return 0;}ans*=a;}cout<<ans<<'\n';}