問題一覧 > 通常問題

No.1243 Divisor Addition

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 192
作問者 : 👑 tute7627 / テスター : ngtkana
お気に入りにしたユーザー ProblemId : 4442 / 自分の提出
問題文最終更新日: 2020-08-28 16:29:50
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 268 (順位表) の他の問題:

Problem Statement

You are given integers $A,B$. You may perform the following operation on the integer $A$ up to $120$ times.

  • Choose one positive divisor of $A$ and add it to $A$.
Construct one sequence of operations that makes $A$ and $B$ equal.
It can be shown that under the constraints of this problem, a sequence of operations satisfying the condition always exists.

You are given $T$ test cases.

Input

$T$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_T\ B_T$

Line $1$ contains the number of test cases $T$.
Each of the following $T$ lines contains integers $A_i,B_i$ separated by a space.

  • All inputs are integers.
  • $1 \le T \le 100$
  • $1 \le A_i < B_i \le 10^{18}$

Output

Print $2T$ lines.
On line $2i - 1$, print the number of operations $K(1 \le K \le 120)$ for the $i$-th test case.
On line $2i$, print the integers $X_1 \ X_2 \dots X_K$ chosen in the operations for the $i$-th test case, separated by spaces.
$X_j$ is the integer added to $A_i$ in the $j$-th operation, and it must be a positive divisor of $A_i$ after the $j-1$-th operation.
Print a newline at the end.

Sample

Sample 1
Input
2
26 57
100000000000 200000000000
Output
4
1 9 2 19
1
100000000000

In test case $1$, $A$ changes as $26 \to 27 \to 36 \to 38 \to 57$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。