2022年CSP-J复赛真题解析

作者：赵京龙

1.
乘方​

这道题看似简单，但稍不留神就会出错，要求选手具备全面思考问题的能力。​

•
易错点1：如何判断结果超出
?​
计算
最直观的做法是使用循环来计算
个
相乘，但一定要注意，千万不要等
个
相乘结束后再去判断结果是否达到
！因为循环过程中当结果超过
（这里假设你定义的数据类型是long long类型）后，就发生了溢出，结果已经出错。解决方法是在循环过程中，每次将结果乘上一个
，就判断一下结果是否大于等于
，如果是，立即结束循环，并输出-1。​

•
易错点2：如何避免超时？​
注意题目中描述的取值范围：
。在大多数题目中，循环的复杂度达到
（也就是循环中的计算次数），就会导致程序超时而无法满分通过题目。不妨回想一下，当
时，
取多少，有
？不必太准确，我们至少能知道，当
时，就必有
。其实题目描述中给出了这个提示，int类型是32位整数类型（最高位是符号位，故仅31位表示数字），能表示的最大整数是
，
用不着多么大，
的结果就已经超出
了。再想一下，当
时，
取多少，有
？不必精确计算，显然当
时，就必有
。​
实际上，直接特判
也可以避免超时，因为
时，当结果超过
时就提前结束了循环。​

只要考虑到上面两个易错点，这道题目就是签到题了。

代码块

#include <bits/stdc++.h>​
using namespace std;​
​
int main() {​
    long long a, b;​
    cin >> a >> b;​
    if (b >= 32)  // b>=32, 结果必超出1e9​
        cout << -1 << endl;​
    else {​
        long long res = 1;​
        while (b--) {​
            res *= a;​
            if (res >= 1000000000) {​
                res = -1;​
                break;​
            }​
        }​
        cout << res << endl;​
    }​
}​

2.
解密​

这道题是多组输入，不同组之间没有任何联系。对于每一组输入，有三个值
。题目要求我们求出两个数字
，满足：​

用(2)式-(1)式可以得出如下形式：

如果把
看作一元二次方程的两个根，那么上两式满足韦达定理，也就是说
是某个一元二次方程的根。实际上，我们只需要求解上面这个联合方程，就可以求出
的值。不妨将
代入(1)式，可得
，用
替换
并整理可得：​

显然，该方程满足(3)(4)式的韦达定理，那么
就是该方程的两个根，整个题目的问题转化为求解这个一元二次方程。​

通过下式判断方程是否有实数根，

若

，方程无实数根，即实数域内无解；

若

，方程有实数根，两根分别为：

•
易错点1：题目要求
是整数，所以我们求出的解必须是整数，并且还要验证是否满足原方程（验证是否满足(1)(2)式即可）。​

•
易错点2：注意数据范围。该题计算过程中涉及的
数值可达
，而C++库为我们提供的开方函数sqrt()是针对浮点数计算的，double类型有效位数至多17位，那么使用sqrt()计算会导致数值较大的方程出错，从而无法获得这道题的分数。那怎么办呢？自己动手写开方方法，方法众多，该题解以二分法为例求出。​

代码块

#include <bits/stdc++.h>​
using namespace std;​
​
// 二分法求x的二次根​
long long my_sqrt(long long x) {​
    long long L = 0, R = 1e9 + 7, M;​
    while (L < R) {​
        M = (L + R) >> 1;​
        if (M * M < x)​
            L = M + 1;​
        else​
            R = M;​
    }​
    return R;  // R*R>=x​
}​
​
int main() {​
    long long k, n, d, e, p, q, delta;  // 为避免浮点数误差，均采用长整型​
    scanf("%lld", &k);​
    while (k--) {​
        scanf("%lld %lld %lld", &n, &d, &e);​
        delta = (n - e * d + 2) * (n - e * d + 2) - 4 * n;​
        if (delta < 0) {​
            puts("NO");​
        } else {​
            p = (n - e * d + 2 - my_sqrt(delta)) / 2;​
            q = (n - e * d + 2 + my_sqrt(delta)) / 2;​
            if (p * q == n && (p - 1) * (q - 1) + 1 == e * d)  // 验证​
                printf("%lld %lld\n", p, q);​
            else​
                puts("NO");​
        }​
    }​
}​
​

2022年CSP-J复赛真题解析​

2022年CSP-J复赛真题解析