← 返回题目列表

AtCoder · arc191_c

C. A的n次方减1

中文机器翻译题面 查看原题

分数: 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).