No.3037 トグルトグルトグル！
タグ : / 解いたユーザー数 121
作問者 :
eiram
/ テスター :
Nauclhlt🪷
Blue_S
naniwazu
問題文
$N$人が横一列に座っており、左端の人から順に$1$～$N$までの番号が割り当てられています。
座っている人は立ち、立っている人は座ることをトグルすると言います。
最初の合図ですべての人が立ちます。
次の合図で$2$番の人から$1$人おき($2$,$4$,$6$...)にトグルします。
さらに次の合図では$3$番の人から$2$人おき($3$,$6$,$9$...)にトグルします。
以下同様に$i$回目の合図では$i$の倍数番目の人がトグルします。
そして最後に、$N$回目の合図で、$N$番の人だけがトグルします。
すべての合図が終わった時、立っている人の人数を求めてください。
制約
$・$ $2 \le N \leq 10^{18}$
入力
入力は以下の形式で標準入力から与えられる。$N$
出力
全ての合図が終わった時、立っている人の人数を出力せよ。
サンプル
サンプル1
入力
6
出力
2
最初、$6$人が横一列に座っており、左端から順に$1,2,3,4,5,6$と番号が割り当てられています。
最初の合図で全員が立ち、今立っているのは($1,2,3,4,5,6$)です。
$2$回目の合図で$2,4,6$番の人が座り、今立っているのは($1,3,5$)です。
$3$回目の合図で$3$番の人が座り、$6$番の人が立ちます。今立っているのは($1,5,6$)です。
$4$回目の合図で$4$番の人が立ち、今立っているのは($1,4,5,6$)です。
$5$回目の合図で$5$番の人が座り、今立っているのは($1,4,6$)です。
$6$回目の合図で$6$番の人が座り、今立っているのは($1,4$)です。
最後の合図が終わった時点で立っているのは$2$人なので、2と出力します。
サンプル2
入力
50
出力
7
サンプル3
入力
2000
出力
44
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。