← 返回题目列表

AtCoder · tupc2024_l

L. 方形连接

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

配点 : 100 点

問題文

正整数 s,t 。你可以执行以下操作 您可以执行此操作超过 0 您可以随意执行多次。 小于或等于

  • 1 以上 4 \times 10^{18} 的整数 给出了 u 找出可被 s+u 是平方数的一个, 替换为s 该值应乘以 u 替换为

s 该值应乘以 t 和一种方法所需的最少操作数。

形式上,长度满足以下所有条件 K 整数序列 给出 (u_1,u_2,\dots,u_K) 。 匹配

  • K 是 您也可以写 s 该值应乘以 t 所需的最少操作数
  • i=1,2,\dots,K 反对 1 \leq u_i \leq 4 \times 10^{18}
  • u_0=s 按此顺序输出 i=1,2,\dots,K 反对 u_{i-1}+u_i 是一个平方数
  • u_K=t

在这个问题的约束下, 10^6 通过以下操作: 由于它无法移动到 s 该值应乘以 t 。 您将获得

T 个测试用例,请分别求出答案。 包含在

制約

  • 1 \leq T \leq 3 \times 10^5
  • 1 \leq s, t \leq 10^9
  • s \ne t
  • 1 一个输入文件所需的操作数 (=K) 的总和为 10^6 以下
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

这里 \text{case}_i 是 您也可以写 i 个测试用例,每个测试用例按以下格式给出。

s t

出力

T 行。i 在线 i 按以下格式输出测试用例的答案。

K u_1 u_2 \dots u_K

如果有多个答案,则任何一个输出都将被视为正确。


入力例 1

3
8 3
20 24
998236771 998244353

出力例 1

2 1 3
3 5 76 24
1 998244353
输入 3 8 3 20 24 998236771 998244353 输出 2 1 3 3 5 76 24 1 998244353

1 关于第二个测试用例,8+1=9,1+3=4 都是平方数。另外,1 操作 如果你能匹配 8 该值应乘以 3 。 只能使用