2022 T2 解密

主知识点：二分。交叉标签：二分、数学。
暴力标注：不属于重点 DP 退路题。
OJ 使用标准输入与标准输出。原比赛文件名为 decode.in / decode.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 512 MiB；测试点 10；总分 100。
数据来源：公开存档数据；未逐文件对照官网下载包。

题目描述

每次给出正整数 $n,e,d$，寻找正整数 $p\le q$，满足 $pq=n$ 且 $ed=(p-1)(q-1)+1$。若存在则输出 $p,q$，否则输出 NO。

输入格式

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

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

输出格式

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

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

如果无解，请输出 NO。

样例

样例 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

输出：

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$		保证有解
$2$				无
$3$		$10^9$	$6\times 10^4$	保证有解
$4$				无
$5$			$10^9$	保证有解
$6$				无
$7$	$10^5$	$10^{18}$		保证若有解则 $p=q$
$8$				保证有解
$9$				无
$10$

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P8814
• 赛事：CSP-J 第二轮入门级 2022。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。