信息学奥赛一本通 2086：【22CSPJ普及组】乘方(pow) | 洛谷 P8813 [CSP-J 2022] 乘方

【题目链接】

ybt 2086：【22CSPJ普及组】乘方(pow)
洛谷 P8813 [CSP-J 2022] 乘方

【题目考点】

1. 求数字位数

2. 循环 累乘

【解题思路】

解法1：循环求幂

a与b的范围都是$1\sim 10^9$，结果超过$10^9$就输出-1。
两个小于等于$10^9$的数字相乘，结果不会超过$10^{18}$，可以使用long long类型保存该值。
这里使用循环求幂。
注意：a=1，b=$10^9$时，循环求幂会循环$10^9$次，大于$10^8$，会超时。因此当a=1时，应该直接输出1。
设r为累乘乘积，初值为1。如果在循环求幂的过程中，若发现r大于$10^9$，则直接输出-1，而后结束程序。
最后输出乘积r。
复杂度为：$O(b)$

【题解代码】

解法1：循环求幂

#include 
using namespace std;
#define N 105
int main()
{
	long long r = 1;
	int a, b;
	cin >> a >> b;
	if(a == 1)
	{
		cout << 1;
		return 0;
	}
	for(int i = 1; i <= b; ++i)
	{
		r *= a;
		if(r > 1000000000)
		{
			cout << -1;
			return 0;
		}
	}
	cout << r;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25