No.2016 Countdown Divisors
タグ : / 解いたユーザー数 133
作問者 :
milkcoffee
/ テスター :
mink1618033
問題文
最初、黒板に $1$ つの正整数 $N$ が書かれています。
黒板に正整数 $x$ が書かれているとき、あなたは $x$ の正の約数の個数を $d(x)$ として、黒板の整数を $x-d(x)$ に書き換えるという操作を行います。
例えば、黒板に $6$ が書かれているとき、 $6$ の正の約数の個数は $4$ なので、黒板の数を $2$ に書き換えます。
黒板に書かれた整数が $0$ になるまで操作を繰り返し、 $0$ になったら操作を終了します。(操作を繰り返すと必ず黒板の整数が $0$ になることが証明できます。)
$0$ になる直前に黒板に書かれている正整数を求めてください。
$T$ 個のテストケースについて答えてください。
入力
$T$ $case_1$ $case_2$ $\vdots$ $case_T$ただし、 $case_i$ は $i$ 番目のテストケースを表す。
各テストケースは以下の形式で与えられる。
$N$
- $1 \leq T \leq 10^5$
- $1 \leq N \leq 10^9$
- 入力は全て整数である。
出力
$0$ になる直前に黒板に書かれる整数を出力してください。
$i$ 番目のテストケースに対する答えを $i$ 行目に出力してください。
サンプル
サンプル1
入力
3 6 1 3
出力
2 1 1
$1$ つ目のケースについて、最初は黒板に $6$ が書かれています。
$6$ の正の約数の個数は $4$ です。 $6-4=2$ であるため、 $2$ に書き換えます。
$2$ の正の約数の個数は $2$ です。 $2-2=0$ であるため、 $0$ に書き換えます。
$0$ になったため操作を終了します。$0$ の直前に書かれていた整数は $2$ です。
$2$ つ目のケースについて、最初は黒板に $1$ が書かれています。
$1$ の正の約数の個数は $1$ です。$1-1=0$ であるため、 $0$ に書き換えます。
$0$ になったため操作を終了します。$0$ の直前に書かれていた整数は $1$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。