問題一覧 > 通常問題

No.3037 トグルトグルトグル！

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

問題文

NN人が横一列に座っており、左端の人から順に11～NNまでの番号が割り当てられています。

座っている人は立ち、立っている人は座ることをトグルすると言います。

最初の合図ですべての人が立ちます。
次の合図で22番の人から11人おき(22,44,66...)にトグルします。
さらに次の合図では33番の人から22人おき(33,66,99...)にトグルします。
以下同様にii回目の合図ではiiの倍数番目の人がトグルします。
そして最後に、NN回目の合図で、NN番の人だけがトグルします。

すべての合図が終わった時、立っている人の人数を求めてください。

制約

・・ 2≤N≤10182 \le N \leq 10^{18}

入力

入力は以下の形式で標準入力から与えられる。 
NN

出力

全ての合図が終わった時、立っている人の人数を出力せよ。

サンプル

サンプル1
入力
6
出力
2

最初、66人が横一列に座っており、左端から順に1,2,3,4,5,61,2,3,4,5,6と番号が割り当てられています。
最初の合図で全員が立ち、今立っているのは(1,2,3,4,5,61,2,3,4,5,6)です。
22回目の合図で2,4,62,4,6番の人が座り、今立っているのは(1,3,51,3,5)です。
33回目の合図で33番の人が座り、66番の人が立ちます。今立っているのは(1,5,61,5,6)です。
44回目の合図で44番の人が立ち、今立っているのは(1,4,5,61,4,5,6)です。
55回目の合図で55番の人が座り、今立っているのは(1,4,61,4,6)です。
66回目の合図で66番の人が座り、今立っているのは(1,41,4)です。
最後の合図が終わった時点で立っているのは22人なので、2と出力します。

サンプル2
入力
50
出力
7

サンプル3
入力
2000
出力
44

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