시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 19 15 12 80.000%

문제

형석이는 너무 심심했기 때문에 큰 원 위에 일정한 간격으로 N개의 못을 박았다. 그리고 어느 한 못을 P0라고 하고, 이 못에서부터 시계방향으로 다른 못들을 P1에서 PN-1이라고 이름 붙였다. 그리고 이 못들을 철사로 연결하는 놀이를 시작했다. 얼마간 이 놀이를 반복하던 형석이는 그렸던 철사들을 모두 없애고 다음과 같이 철사를 연결하기로 했다.

  1. Q0 = P0이라고 하자. 그리고 다음을 1단계에서부터 N2단계까지 반복한다.
  2. p 단계에서는 Qp-1 = Pk이면, Qp = P(k+p) mod n으로 하여, Qp-1에서 Qp까지를 철사로 연결한다. 만약 이미 두 못 이미 연결되어 있다면 연결하지 않는다. 또한, Qp-1과 Qp가 같은 못이라면 연결하지 않는 것으로 취급한다.

형석이가 연결하게 될 철사의 개수는 몇 개가 될 것인지 구해주자.

입력

첫 번째 줄에 자연수 N이 주어진다. (3 ≤ N ≤ 1012)

출력

첫 번째 줄에 형석이가 연결하게 될 철사의 개수를 출력한다.

예제 입력

3

예제 출력

1

예제 입력 2

4

예제 출력 2

3

예제 입력 3

5

예제 출력 3

2

힌트

출처

Contest > kriiicon > 제 2회 kriiICPC W번