j02244. CSP-J 2022 复赛 T2 解密

题目描述

时间限制：1s　内存限制：512MB　来源：洛谷 P8814

题目描述

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

样例

输入

输出

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

j02244. CSP-J 2022 复赛 T2 解密 未做

题目描述

题目描述

输入格式

输出格式

样例

说明/提示

j02244. CSP-J 2022 复赛 T2 解密未做