2022 解密 · 方案一二分求整数平方根

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

化成一元二次方程，二分开方没有浮点误差

2022
数学

正文

// CSP-J 2022 复赛 T2 · 解密
// 原题：https://oj.yecheng.tv/p/CSPJ2022B
// 题意：每组给 n、d、e，要找正整数 p、q 使得
//   n = p * q  且  e * d = (p - 1)(q - 1) + 1
// 把第二式展开：e*d = p*q - p - q + 2，代入 p*q = n，得到
//   p + q = n - e*d + 2
// 于是问题变成「已知两数之和 m 与两数之积 n，求这两个数」，解一元二次方程：
//   p、q 是 x^2 - m*x + n = 0 的两根，判别式 delta = m^2 - 4*n = (p - q)^2。
// 所以 delta 必须是一个完全平方数，且 (m - sqrt(delta)) 还得是偶数。
//
// 方案一 · 二分求整数平方根（完全避开浮点误差）
// 自己写 isqrt(x)：返回不超过 sqrt(x) 的最大整数，用二分实现，
// 比较时写成 mid <= x / mid 而不是 mid * mid <= x，这样连溢出都一起躲掉了。
// n 能到 1e18，但题目保证 m = n - e*d + 2 不超过 1e9，
// 所以 m * m 最多 1e18，long long（约 9.2e18）装得下。

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

long long isqrt(long long x) {
    long long l = 0, r = 1000000000LL;      // sqrt(1e18) 正好是 1e9
    while (l < r) {
        long long mid = (l + r + 1) / 2;
        if (mid <= x / mid) l = mid;        // mid^2 <= x，用除法比较不溢出
        else r = mid - 1;
    }
    return l;
}

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;        // 这就是 p + q
        long long delta = m * m - 4 * n;    // 这就是 (p - q)^2

        if (delta < 0) {
            cout << "NO\n";
            continue;
        }
        long long s = isqrt(delta);
        if (s * s != delta) {               // 判别式不是完全平方数，无整数解
            cout << "NO\n";
            continue;
        }
        if ((m - s) % 2 != 0) {             // 除以 2 要能整除
            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 解密 · 方案一二分求整数平方根