問題一覧 > 通常問題

No.3037 トグルトグルトグル!

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 121
作問者 : eiram / テスター : Nauclhlt🪷 Blue_S naniwazu
5 ProblemId : 11807 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-12 23:23:07

問題文

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