csp-j 2022题解

T1 pow

LL power (int a, int b) {
   
	LL result = 1;
	while (b -- ) result = (LL)result * a;
	return result;
}
int main ( ) {
   
typedef long long LL;
int a, b; cin >> a >> b;
LL result = (LL)power (a, b);
cout << (result > 1000000000? -1: result);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

$显然这不是正解，两个问题：$

1.时间复杂度
2.10⁹的10⁹次方会爆掉

解决第一个，快速幂可以解决（毕竟10⁹的log才20左右）

LL power (int a, int b) {
   
	LL result = 1;
	while (b) {
   
		if (b & 1) result = (LL)result * a;
		a = (LL)a * a;
		b >>= 1;
	}
	return result;
}
int main ( ) {
   
typedef long long LL;
int a, b; cin >> a >> b;
LL result = (LL)power (a, b);
cout << (result > 1000000000? -1: result);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

可是10⁹的10⁹次方还是会爆掉，所以暴力求a^b，在过程中判断。

LL result = 1;
for (int i = 1; i <= b; i ++ ) {
    
	result = (LL)result * a;
	if (result > 1000000000) {
    
		cout << -1;
		return 0;
	}
} cout << result;
1
2
3
4
5
6
7
8
9
10

试一下极限数据（a=10⁹，b=10⁹）：

i=1, result=10⁹
i=2, result=10¹⁸, 还没爆掉，10¹⁸>10⁹，结束，输出-1

水题拿下。

#include 
#define FOR(i, a, b) for(int i = a; i <= b; i ++ )
#define DOR(i, a, b) for(int i = b; i >= a; i -- )
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
int a, b;
LL res = 1;
int main () {
   
	freopen ("pow.in", "r", stdin);
	freopen ("pow.out", "w", stdout);
	cin >> a >> b;
	for (int i = 
1
2
3
4
5
6
7
8
9
10
11
12
13