4100 : 흑백 돌 뒤집기2
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 13
•통과: 4
•만든사람: suakii
문제 설명
1부터 $N$까지의 번호가 매겨진 $N$개의 돌이 일렬로 놓여 있습니다.
처음에는 모든 돌의 상태가 흰색($0$)입니다.
단계 $K$ ($1 \le K \le N$)마다 $K$의 배수 번호를 가진 돌들의 상태를 뒤집습니다.
돌을 뒤집으면 흰색($0$)은 검은색($1$)이 되고, 검은색($1$)은 흰색($0$)이 됩니다.
모든 단계($K = 1, 2, \dots, N$)를 마친 후, 검은색($1$) 상태인 돌의 개수를 출력하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 10^{12}$
• $N$은 정수
처음에는 모든 돌의 상태가 흰색($0$)입니다.
단계 $K$ ($1 \le K \le N$)마다 $K$의 배수 번호를 가진 돌들의 상태를 뒤집습니다.
돌을 뒤집으면 흰색($0$)은 검은색($1$)이 되고, 검은색($1$)은 흰색($0$)이 됩니다.
모든 단계($K = 1, 2, \dots, N$)를 마친 후, 검은색($1$) 상태인 돌의 개수를 출력하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 10^{12}$
• $N$은 정수
입력 설명
첫째 줄에 돌의 개수 주어집니다.
출력 설명
최종 상태에서 검은색($1$)인 돌의 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3