A775 | $[CSP-J 2022] 解密$

来源CSP-J / 2022

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个正整数 $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。

输入 #1

输出 #1

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$无

测试点编号	$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$	无

C++ 编辑器

输入

输出