← 返回题目列表

AtCoder · arc158_d

D. 方程

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

分数: 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},因此满足条件。