PDF文档公众号回复关键字:20241012
此前解析题，P8813 [CSP-J 2022] 乘方，给出了循环的解题思路，当时在洛谷提交是通过的，后台收到留言，a=1,b=1e9会炸吧？，确实啊整除要求1s内循环次数最大可以到10^7,现在测试数据明显大很多，按测试数据有这个可能，没想到CSP普及组第1题竟然翻车，去CCF官网去找测试数据，竟然没有2022年的测试数据，去另外一个OJ上面测试了一下，竟然有超时测试用例
提交原码
#include<bits/stdc++.h>
using namespace std;
const int N=1e9;//允许的最大值 超出输出-1
int a,b;//输入a b
long long m=1;//存储 a^b
int main(){
cin>>a>>b;//输入a b
for(int i=0;i<b;i++){//循环b次
m=m*a;//m从1开始每次乘以a
if(m>N){//如果大于允许的最大值 输出-1
cout<<"-1";
return 0;//退出程序
}
}
cout<<m;//输出 a^b
return 0;
}
分析
确实a=1的时候，b可以比较大，最后也需要循环结束才计算出结果，如果a不是1，循环次数就大大减少
可以分情况讨论 a=1和a!=1
下面给出3种方法
1 循环特判
#include<bits/stdc++.h>
using namespace std;
const int N=1e9;//允许的最大值 超出输出-1
int a,b;//输入a b
long long m=1;//存储 a^b
int main(){
cin>>a>>b;//输入a b
if(a==1){
cout<<"1";
return 0;
}
for(int i=0;i<b;i++){//循环b次
m=m*a;//m从1开始每次乘以a
if(m>N){//如果大于允许的最大值 输出-1
cout<<"-1";
return 0;//退出程序
}
}
cout<<m;//输出 a^b
return 0;
}
2 用快速幂解法
如下用快速幂改造后的程序，不在超时，可以顺利通过
#include <bits/stdc++.h>
using namespace std;
const int N=1e9;
long long a,b,ans=1;
long long quickpow(long long a, long long b) {
while (b) {
if (b & 1) {
ans = ans * a;
}
if(a>N) return -1;
if (ans > N) return -1;
a *= a;
b >>= 1;
}
return ans;
}
int main() {
cin >> a >> b;
cout << quickpow(a, b) << endl;
return 0;
}
/*
输入
1 992465817
输出
1
*/
普及组第1题用快速幂有点过分了，看看还有没有其他解法
3 pow函数解法
#include<bits/stdc++.h>
using namespace std;
const int N=1e9;//允许的最大值 超出输出-1
int a,b;//输入a b
double ans;
int main(){
cin>>a>>b;//输入a b
ans=pow(a,b);
if(ans>N){
cout<<-1<<endl;
}else{
cout<<(int)ans;//输出 a^b
}
return 0;
}
/*
输入
1 992465817
输出
1
*/
可以顺利通过
这里顺便说一些pow函数
C++中有自带的pow()函数，具有求指定底数的指定幂值。通常使用该函数求解幂
实现原理为快速幂，时间复杂度为O(logN)
#include<iostream>
#include<cmath>
using namespace std;
/*
pow函数
该函数接收两个参数，base 为要取次方的数，exponent 为指数。返回结果为 base 的 exponent 次方
double x =pow(base,exponent);
pow=(2,3)=8
*/
int main(){
int base=2;
int exponent=3;
double x=pow(base,exponent);
cout<<x<<endl;
exponent=4;
x=pow(base,exponent);
cout<<x<<endl;
return 0;
}
/*
输出
8
16
*/
如下为原题
[题目描述]
小文同学刚刚接触了信息学竞赛，有一天她遇到了这样一个题：给定正整数 a 和 b，求 a^b 的值是多少。
a^b 即 b 个 a 相乘的值，例如 2^3 即为 3 个 2 相乘，结果为 2×2×2=8
“简单！”小文心想，同时很快就写出了一份程序，可是测试时却出现了错误
小文很快意识到，她的程序里的变量都是 int 类型的。在大多数机器上，int 类型能表示的最大数为 2^31−1，因此只要计算结果超过这个数，她的程序就会出现错误
由于小文刚刚学会编程，她担心使用 int 计算会出现问题。因此她希望你在 ab 的值超过 10^9 时，输出一个 -1 进行警示，否则就输出正确的 a^b 的值
然而小文还是不知道怎么实现这份程序，因此她想请你帮忙
[输入格式]
输入共一行，两个正整数 a,b
[输出格式]
输出共一行，如果 a^b 的值不超过 10^9，则输出 a^b 的值，否则输出 -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。