2022年CSP-J第二轮真题源码解析
个人解析，非评分标准答案。
1. T1 [CSP-J 2022]乘方
【题目描述】
小文同学刚刚接触了信息学竞赛，有一天她遇到了这样一个题：给定正整数
a和 b，求ab的值是多少。
ab即b个a相乘的值，例如23即为3个2相乘，结果为2×2×2=8。
“简单！”小文心想，同时很快就写出了一份程序，可是测试时却出现了错误。小文很快意识到，她的程序里的变量都是 int类型的。在大多数机器上，int类型能表示的最大数为231-1，因此只要计算结果超过这个数，她的程序就会出现错误。
由于小文刚刚学会编程，她担心使用int计算会出现问题。因此她希望你在ab的值超过 109时，输出一个-1进行警示，否则就输出正确的ab的值。然而小文还是不知道怎么实现这份程序，因此她想请你帮忙。
【输入格式】
输入共一行，两个正整数a，b。
【输出格式】
输出共一行，如果ab的值不超过109，则输出ab的值，否则输出-1。
【输入输出样例】
输入#1
10 9
输出#1
1000000000
输入#2
23333 66666
输出#2
-1
【说明/提示】
对于10%的数据，保证b=1。
对于30%的数据，保证b≤2。
对于60%的数据，保证b≤30，ab≤1018。
对于100%的数据，保证1≤a,b≤109。
参考源码：
1. #include
2. using namespace std;
3. #define ll long long int
4. const ll c = 1e9;
5. ll f(ll a, ll b) {
6. ll ret = 1;
7. if (a==1) return 1;
8. for (ll i = 1; i <= b; i++) {
9. ret *= a;
10. if (ret > c) {
11. ret = -1;
12. break;
13. }
14. }
15. return ret;
16. }
17. int main() {
18. ll a, b;
19. cin >> a >> b;
20. cout << f(a, b) << endl;
21. return 0;
22. }
算法思路：
这道题如何从算法的角度来看，计算ab直接累乘即可：b个a相乘，或者直接用快速幂算法来计算。但是这题要考查的核心不是时间复杂度，而是参数范围和返回值的范围问题（题目中已经提示了）。
先分析一下题目会不会出现TLE(Time Limit Exceeded)问题。ab的值不超过109，int型变量的最大值为231-1（231-1>109），也就是说当a≥2，最多循环32次就超过了int型的范围，当然也超过了109范围。所以无需考虑时间复杂度，自然也就不需要采用快速幂算法。
下面讨论越界问题。可以在每次累乘的时间判断结果是否大于109，大于则返回-1，结束循环。这里面有一个问题需要考虑：假设n次累乘的结果小于109，n+1次累乘的结果大概在什么范围内？由于a≤109，n+1次累乘的结果（中间结果）有可能int越界，但是不可能long long int越界(109×109)，所以需要将相关的变量设置为long long int，而不能用int型，防止出现整数上溢出问题。在上面程序中，将(a,b,ret)三个变量设置为long long int，至于为什么要将a和b也设置为long long int（b可以不设置），具体案例可看下面测试代码：
1. #include
2. using namespace std;
3. int main(){
4. long long int a=1e+9;
5. long long int b=1e+9;
6. //不溢出
7. cout<
2. #include
3. using namespace std;
4. #define ll long long int
5. int main() {
6. ll k,n,e,d,m;
7. ll p,q;
8. ll temp1,temp2,root;
9. cin>>k;
10. for(ll i=1;i<=k;i++){
11. cin>>n>>e>>d;
12. m=n-e*d+2;
13. temp1=m*m-4*n;
14. root=sqrt(temp1);
15. if (root*root!=temp1){
16. cout<<"NO"<
2. using namespace std;
3. #define ll long long int
4. int main() {
5. ll k, n, e, d, m;
6. ll p, q;
7. cin >> k;
8. for (ll i = 1; i <= k; i++) {
9. cin >> n >> e >> d;
10. m = n - e * d + 2;
11. ll begin = 1, end = m / 2;
12. ll area;
13. while (begin <= end) {
14. p = (begin + end) / 2;
15. q = m - p;
16. area = p * q;
17. if (area < n) {
18. begin = p + 1;
19. } else if (area > n) {
20. end = p - 1;
21. } else {
22. cout << p << " " << q << endl;
23. break;
24. }
25. }
26. if (begin > end) {
27. cout << "NO" << endl;
28. }
29. }
30. return 0;
算法思路2：
二分法。由于p<=q，p的二分区间是1,m2，判断条件是pq是否大于、等于或者小于n。能采用二分法的原因是：根据p+q=m,pq=n，可以推导出-p-m22+m24=n，n与p是之间的关系是单调递减。
上述算法一次计算的时间复杂度是olog2m2=olog2m-1。可以简单估最大计算次数，由于m的最大值为109，32位2进制最多能表示232个数，232大于109，因此最大计算次数是不会超过31次。
下面分析暴力算法存在的问题。由于pq=n，因此可以将暴力算法的枚举次数优化为n，用p+q=m对每次枚举进行判断。n的最大值为1018，所以一次计算的最大次数为109，这就会出现TLE问题。暴力算法的源码如下：
1. #include
2. using namespace std;
3. #define ll lon