[CSP-J 2022] 解密

共计 1135 个字符，预计需要花费 3 分钟才能阅读完成。

题目

给定一个正整数 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 \leq q_i。
如果无解，输出 NO。

样例

输入

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

输出

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

数据范围

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

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

答案

#pragma GCC optimize(3, "Ofast", "inline")
#include <iostream>
using namespace std;

int k;
long long n, e, d, m, l, r, p, q, t;

int main(){ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> k;
    while(k--){
        cin >> n >> d >> e;
        m = n-e*d+2;
        l = 1;
        r = m/2;
        while(l<=r){p = (l+r)>>1;
            q = m - p;
            t = p*q;
            if(t==n) break;
            else if(t<n) l = p+1;
            else r = p-1;
        }
        if(t==n) cout << p << " " << q << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

解析

找到关系之后简单粗暴二分查找。也可以用一元二次方程求根公式。