分数: 800 点
问题陈述
给你一个正整数 n,和一个素数 p 至少 5.
查找整数三元组 (x,y,z) 满足以下所有条件。
- 1\leq x < y < z \leq p - 1.
- (x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) \equiv x^{3n}+y^{3n}+z^{3n}\pmod{p}.
可以证明这样的三元组 (x,y,z) 始终存在。
你有 T 测试用例解决。
约束
- 1\leq T\leq 10^5
- 1\leq n\leq 10^9
- p 是满足的质数 5\leq p\leq 10^9.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\vdots
\text{case}_T
每个案例的格式如下:
n p
输出
打印 T 行。的 i- 第行应包含 x,y,z 之间有空格 (x,y,z) 是一个解决方案 i- 第一个测试用例。
如果存在多个解决方案,您可以打印其中任何一个。
示例输入 1
3 1 7 2 7 10 998244353
示例输出 1
1 4 6 1 2 5 20380119 21549656 279594297
对于第一个测试用例:
- (x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) = (1+4+6)(1+4+6)(1+16+36) = 6413,和
- x^{3n}+y^{3n}+z^{3n} = 1 + 64 + 216 = 281.
我们有 6413\equiv 281\pmod{7},因此满足条件。