2986 - 解密 [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 \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 \leq {10}^{18}，1 \leq e_i \times d_i \leq {10}^{18} ，1 \leq m \leq {10}^9。
| 测试点编号 | k \leq | n \leq | m \leq | 特殊性质 |
|---|---|---|---|---|
| 1 | 10^3 | 10^3 | 10^3 | 保证有解 |
| 2 | 10^3 | 10^3 | 10^3 | 无 |
| 3 | 10^3 | 10^9 | 6\times 10^4 | 保证有解 |
| 4 | 10^3 | 10^9 | 6\times 10^4 | 无 |
| 5 | 10^3 | 10^9 | 10^9 | 保证有解 |
| 6 | 10^3 | 10^9 | 10^9 | 无 |
| 7 | 10^5 | 10^{18} | 10^9 | 保证若有解则 p=q |
| 8 | 10^5 | 10^{18} | 10^9 | 保证有解 |
| 9 | 10^5 | 10^{18} | 10^9 | 无 |
| 10 | 10^5 | 10^{18} | 10^9 | 无 |
来源
csp-j 2022 T2
标签
