問題一覧 > 通常問題

No.1243 約数加算

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 190
作問者 : 👑 tute7627tute7627 / テスター : ngtkanangtkana
36 ProblemId : 4442 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-28 16:29:50

問題文

整数 $A,B$ が与えられます。 あなたは以下の操作を整数 $A$ に対して $120$ 回まで行うことができます。

  • $A$ の正の約数を一つ選び、$A$ に足す。
$A$ と $B$ が等しくなるような手順を一つ構成してください。
なお、この問題の制約下で条件を満たすような手順が必ず存在することが示せます。

$T$ 個のテストケースが与えられます。

入力

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

$1$ 行目にテストケースの個数 $T$ が与えられます。
続く $T$ 行については、整数 $A_i,B_i$ が空白区切りで与えられます。

  • 入力は全て整数である。
  • $1 \le T \le 100$
  • $1 \le A_i < B_i \le 10^{18}$

出力

$2T$ 行出力してください。
$2i - 1$ 行目には $i$ 個目のテストケースにおいて操作を行う回数 $K(1 \le K \le 120)$ を出力してください。
$2i$ 行目には $i$ 個目のテストケースにおいて操作時に選ぶ整数 $X_1 \ X_2 \dots X_K$ を空白区切りで出力してください。
$X_j$ は $j$ 回目の操作で $A_i$ に足す整数であり、$j-1$ 回目の操作後の $A_i$ の正の約数である必要があります。
最後に改行してください。

サンプル

サンプル1
入力
2
26 57
100000000000 200000000000
出力
4
1 9 2 19
1
100000000000

$1$ 個目のテストケースでは、$A$ は $26 \to 27 \to 36 \to 38 \to 57$ と変化します。

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