問題一覧 > 通常問題

No.3037 Toggle Toggle Toggle!

レベル : / AI推定難易度 : 525 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 136
作問者 : eiram / テスター : nauclhlt Blue_S naniwazu
お気に入りにしたユーザー ProblemId : 11807 / 自分の提出
問題文最終更新日: 2025-02-12 23:23:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 458 (順位表) の他の問題:

Problem Statement

$N$ people are sitting in a row, and they are assigned the numbers $1$ to $N$ in order starting from the leftmost person.

A sitting person standing up and a standing person sitting down is called toggling.

At the first signal, all the people stand up.
At the next signal, starting from person $2$, every $1$ person is skipped ($2$,$4$,$6$...) and those people toggle.
At the signal after that, starting from person $3$, every $2$ people are skipped ($3$,$6$,$9$...) and those people toggle.
Similarly, at the $i$-th signal, the people whose numbers are multiples of $i$ toggle.
Finally, at the $N$-th signal, only person $N$ toggles.

Find the number of people standing when all the signals have finished.

Constraints

$・$ $2 \le N \leq 10^{18}$

Input

The input is given from standard input in the following format.
$N$

Output

Output the number of people standing when all the signals have finished.

Sample

Sample 1
Input
6
Output
2

Initially, $6$ people are sitting in a row, assigned the numbers $1,2,3,4,5,6$ in order from the left end.
At the first signal everyone stands up, and those now standing are ($1,2,3,4,5,6$).
At the $2$-nd signal, persons $2,4,6$ sit down, and those now standing are ($1,3,5$).
At the $3$-rd signal, person $3$ sits down and person $6$ stands up. Those now standing are ($1,5,6$).
At the $4$-th signal, person $4$ stands up, and those now standing are ($1,4,5,6$).
At the $5$-th signal, person $5$ sits down, and those now standing are ($1,4,6$).
At the $6$-th signal, person $6$ sits down, and those now standing are ($1,4$).
When the last signal has finished, $2$ people are standing, so output 2.

Sample 2
Input
50
Output
7

Sample 3
Input
2000
Output
44

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