問題一覧 > 通常問題

No.2016 Countdown Divisors

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 109
作問者 : milkcoffeemilkcoffee / テスター : mink1618033mink1618033
11 ProblemId : 8047 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-03 22:54:45

問題文

最初、黒板に $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もしくは右上の雲マークをクリックしてアカウントを作成してください。