2022 解密 · 方案二先估后校开方

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 1278 字

用 sqrtl 估一下，再用 while 校正回来

2022
数学

正文

// CSP-J 2022 复赛 T2 · 解密（方案二）
// 原题：https://oj.yecheng.tv/p/CSPJ2022B
//
// 方案二 · 用库函数开方，再就地校正
// 思路与方案一完全相同，只是开平方改用 sqrtl（long double 版本）。
// 关键点：浮点开方可能有 1 的误差，绝不能直接信，一定要「就地校正」两步：
//   先 while (s * s > x) s--，再 while ((s+1) * (s+1) <= x) s++。
// 校正之后 s 就是精确的整数平方根，再判 s * s == x 即可。
// 这个「先估后校」的套路在很多题目里都能用，比手写二分短，但要记得校正。

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("decode.in", "r", stdin);
    freopen("decode.out", "w", stdout);

    int k;
    cin >> k;
    while (k--) {
        long long n, d, e;
        cin >> n >> d >> e;
        long long m = n - e * d + 2;
        long long delta = m * m - 4 * n;

        if (delta < 0) {
            cout << "NO\n";
            continue;
        }
        long long s = (long long)sqrtl((long double)delta);
        while (s * s > delta) s--;                   // 估大了往回退
        while ((s + 1) * (s + 1) <= delta) s++;      // 估小了往前补
        if (s * s != delta) {
            cout << "NO\n";
            continue;
        }
        if ((m - s) % 2 != 0) {
            cout << "NO\n";
            continue;
        }
        long long p = (m - s) / 2;
        long long q = (m + s) / 2;
        if (p >= 1 && p * q == n) cout << p << " " << q << "\n";
        else cout << "NO\n";
    }
    return 0;
}

2022 解密 · 方案二 先估后校开方

正文

CSP-J 标程 · 复赛真题的其它内容

2022 解密 · 方案二先估后校开方