#P10773. [POI 2019] Najmniejsza wspólna wielokrotność / 最小公倍数

    ID: 9895 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 7 上传者: 标签>CF2300提高+/省选-最小公倍数欧几里得算法二分查找奇偶分组有限候选集缩减暴力枚举离线查询

[POI 2019] Najmniejsza wspólna wielokrotność / 最小公倍数

题目背景

Byteasar 正在准备他的数学考试。

题目描述

老师跟他说考试题目中有关于最小公倍数 lcm\rm lcm 的题目,于是他找到了一道题练练手。

给定一个整数 MM,求一个区间 [a,b][a,b] 使得 MM 为这个区间所有数的最小公倍数。

因为您很强,所以 Byteasar 在解出来这道题的同时也想问问您这题的答案。

因为 Byteasar 非常爱问问题,所以他要问您 zz 组问题。

输入格式

第一行一个整数 zz 代表询问个数。
接下来 zz 行每行一个整数 MM 代表一个询问。

输出格式

zz 行每行两个整数 a,ba,b 代表一个询问的答案。
如果有多组解:

  • 输出 aa 最小的
  • 如果还有多组解输出 bb 最小的

输入输出样例 #1

输入 #1

3
12
504
17

输出 #1

1 4
6 9
NIE

输入输出样例 #2

输入 #2

5
5
6
7
8
9

输出 #2

NIE
1 3
NIE
NIE
NIE

输入输出样例 #3

输入 #3

1
1000000

输出 #3

NIE

输入输出样例 #4

输入 #4

1
99999990000000

输出 #4

9999999 10000000

说明/提示

样例说明

对于样例 11 的第一组数据,1212 为区间 [1,4][1,4] 的最小公倍数。

数据规模与约定

本题采用捆绑测试。

  • Subtask 1(18 pts):z≤10z \le 10,M≤1000M \le 1000。
  • Subtask 2(20 pts):z≤100z\le 100,M≤109M \le 10^9。
  • Subtask 3(20 pts):z≤100z \le 100,M≤1018M \le 10^{18}。
  • Subtask 4(42 pts):无特殊限制。

对于 100%100\% 的数据,1≤z≤1041 \le z\le 10^4,1≤M≤10181 \le M \le 10^{18}。