问题 C: 解密(decode)

内存限制:512 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:410 通过:57

题目描述

给定一个正整数 k,有 k 次询问,每次给定三个正整数 nieidi,求两个正整数 piqi

使 ni=pi×qi, ei×di=(pi−1)(qi−1)+1。

输入格式

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

接下来 k 行,第 i 行三个正整数 nidiei

输出格式

输出 k 行,每行两个正整数 piqi 表示答案。

为使输出统一,你应当保证 pi ≤ qi

如果无解,请输出 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×d+2

保证对于 100% 的数据,1≤k≤105,对于任意的 1 ≤ i ≤ k1 ≤ ni ≤ 1018, 1 ≤ei × di ≤ 1018, 1 ≤ m ≤ 109

测试点编号 k ≤ n ≤ m ≤ 特殊性质
1 103 103 103 保证有解
2
3 109 6 ×104 保证有解
4
5 109 保证有解
6
7 105 1018 保证若有解则 p = q
8 保证有解
9
10

分类标签