分数: 600 点
问题陈述
给你一个正整数 N 之间 1 和 10^9,包括在内。
查找一对正整数 (A, M) 满足以下条件。可以证明这样的一对整数在约束条件下总是存在的。
- 两者 A 和 M 是介于 1 和 10^{18},包括在内。
- 存在一个正整数 n 这样 A^n - 1 是的倍数 M,最小的这样 n is N.
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1 \le T \le 10^4
- 1 \le N \le 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
在这里, \text{case}_i 表示 i- 第一个测试用例。
每个测试用例均按以下格式给出:
N
输出
对于每个测试用例,打印一对正整数 (A, M) 采用以下格式:
A M
如果有多个有效解,则其中任何一个都被认为是正确的。
示例输入 1
4 3 16 1 55
示例输出 1
2 7 11 68 20250126 1 33 662
考虑 \text{case}_1.
例如,如果我们选择 (A,M)=(2,7),然后:
- 当 选择 n=1: 2^1 - 1 = 1 不是以下的倍数 7.
- 当 选择 n=2: 2^2 - 1 = 3 不是以下的倍数 7.
- 当 选择 n=3: 2^3 - 1 = 7 是的倍数 7.
因此,最小的 n 其中 A^n - 1 是的倍数 M is 3。因此, (A,M)=(2,7) 是正确的解决方案。其他有效的解决方案包括 (A,M)=(100,777).