/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君は、学校の体育館にある N 個のロッカーの管理を任されています。ロッカーには 1 から N までの番号が付けられています。最初、すべてのロッカーは閉まっています。
高橋君はこれから N 回の操作を行います。i 回目（i = 1, 2, \ldots, N）の操作では、番号が i の倍数であるすべてのロッカー（番号 i のロッカー自体も含む）について、開いているものは閉め、閉まっているものは開けます。
例えば、1 回目の操作では番号が 1 の倍数であるロッカー、すなわち 1, 2, \ldots, N 番のすべてのロッカーの開閉状態を切り替えます。2 回目の操作では番号が 2 の倍数である N 以下の番号のロッカー、すなわち 2, 4, 6, \ldots 番のロッカーの開閉状態を切り替えます。3 回目の操作では番号が 3 の倍数である N 以下の番号のロッカー、すなわち 3, 6, 9, \ldots 番のロッカーの開閉状態を切り替えます。
すべての操作が終わった後、開いているロッカーの個数を求めてください。
制約
- 1 \leq N \leq 10^{18}
- N は整数
入力
N
ロッカーの個数を表す整数 N が 1 行で与えられる。
出力
すべての操作が終わった後に開いているロッカーの個数を整数で 1 行に出力せよ。
入力例 1
10
出力例 1
3
入力例 2
100
出力例 2
10
入力例 3
1000000000000000000
出力例 3
1000000000
Score : 333 pts
Problem Statement
Takahashi is in charge of managing N lockers in the school gymnasium. The lockers are numbered from 1 to N. Initially, all lockers are closed.
Takahashi will perform N operations. In the i-th operation (i = 1, 2, \ldots, N), for every locker whose number is a multiple of i (including locker number i itself), he toggles its state: if it is open, he closes it, and if it is closed, he opens it.
For example, in the 1st operation, he toggles the state of all lockers whose numbers are multiples of 1, namely lockers 1, 2, \ldots, N. In the 2nd operation, he toggles the state of lockers whose numbers are multiples of 2 and at most N, namely lockers 2, 4, 6, \ldots. In the 3rd operation, he toggles the state of lockers whose numbers are multiples of 3 and at most N, namely lockers 3, 6, 9, \ldots.
After all operations are completed, find the number of lockers that are open.
Constraints
- 1 \leq N \leq 10^{18}
- N is an integer
Input
N
An integer N representing the number of lockers is given on a single line.
Output
Print the number of lockers that are open after all operations are completed, as an integer on a single line.
Sample Input 1
10
Sample Output 1
3
Sample Input 2
100
Sample Output 2
10
Sample Input 3
1000000000000000000
Sample Output 3
1000000000