[CSP-J 2022] 解密（民间数据）

题目描述

给定一个正整数 $k$，有 $k$ 次询问，每次给定三个正整数 $n_i,e_i,d_i$，求两个正整数 $p_i,q_i$，使 $n_i=p_i\times q_i$、$e_i\times d_i=(p_i-1)(q_i-1)+1$。

输入格式

第一行一个正整数 $k$，表示有 $k$ 次询问。

接下来 $k$ 行，第 $i$ 行三个正整数 $n_i,d_i,e_i$。

输出格式

输出 $k$ 行，每行两个正整数 $p_i,q_i$ 表示答案。

为使输出统一，你应当保证 $p_i\le q_i$。

如果无解，请输出 NO。

样例 #1

样例输入 #1

10
770 77 5
633 1 211
545 1 499
683 3 227
858 3 257
723 37 13
572 26 11
867 17 17
829 3 263
528 4 109

样例输出 #1

2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88

提示

【样例 #2】

见附件中的 decode/decode2.in 与 decode/decode2.ans。

【样例 #3】

见附件中的 decode/decode3.in 与 decode/decode3.ans。

【样例 #4】

见附件中的 decode/decode4.in 与 decode/decode4.ans。

【数据范围】

以下记 $m=n-e\times d+2$。

保证对于 $100\%$ 的数据，$1\le k\le {10}^5$，对于任意的 $1\le i\le k$，$1\le n_i\le {10}^{18}$，$1\le e_i\times d_i\le {10}^{18}$
，$1\le m\le {10}^9$。

分析

1. 题目第一眼，想的是枚举p,q，但是一看数据就知道会tle，然后就要看题目，试着去变形式子，经过变换可得关于p、q的两根之积、两根之和的式子，就是韦达定理，这是解这个题的核心；然后构造关于p、q的一元二次方程求根即可；
2. 通过判别式b^2-4ac的正负判断是否有根，存在根的话，用求根公式解出根；由于题目要求根为整数，可能这个方程的根为小数，我们取整后，要带进原等式判断是否成立；
   

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll k, n, d, e;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> k;
    while (k--) {
        cin >> n >> d >> e;
        //表示b^2-4ac
        ll b = (n - e * d + 2) * (n - e * d + 2) - 4 * n;
        if (b < 0)
            cout << "NO" << endl;
        else {
            //不但有根，还要保证根为整数
            ll p = (n - e * d + 2 - (long long) sqrt(b)) / 2;
            ll q = (n - e * d + 2 + (long long) sqrt(b)) / 2;
            //验证下原式，是否符合，即判断了根是否为整数
            if (p * q == n && n - e * d + 2 == p + q)
                cout << (n - e * d + 2 - (long long) sqrt(b)) / 2 << " " << (n - e * d + 2 + (long long) sqrt(b)) / 2
                     << endl;
            else
                cout << "NO" << endl;
        }
    }
    return 0;
}