Wiring Batch
Time limit | Memory limit | # of submissions | # of submitted users | Solved # | Accepted user ratio |
---|---|---|---|---|---|
1000 ms | 256 MiB | 70 | 34 | 34 | 100.00% |
형석이는 너무 심심했기 때문에 큰 원 위에 일정한 간격으로 $N$개의 못을 박았다. 그리고 어느 한 못을 $P_{0}$라고 하고, 이 못에서부터 시계방향으로 다른 못들을 $P_{1}$에서 $P_{N - 1}$이라고 이름 붙였다. 그리고 이 못들을 철사로 연결하는 놀이를 시작했다. 얼마간 이 놀이를 반복하던 형석이는 그렸던 철사들을 모두 없애고 다음과 같이 철사를 연결하기로 했다.
- $Q_{0} = P_{0}$이라고 하자. 그리고 다음을 1단계에서부터 $N^{2}$단계까지 반복한다.
- $p$ 단계에서는 $Q_{p - 1} = P_{k}$이면, 으로 하여, $Q_{p - 1}$에서 $Q_{p}$까지를 철사로 연결한다. 만약 이미 두 못 이미 연결되어 있다면 연결하지 않는다. 또한, $Q_{p - 1}$과 $Q_{p}$가 같은 못이라면 연결하지 않는 것으로 취급한다.
형석이가 연결하게 될 철사의 개수는 몇 개가 될 것인지 구해주자.
입력 형식
첫 번째 줄에 자연수 $N$이 주어진다.
쉬운 문제에서는 $3 \le N \le 1,000$인 입력이 주어진다.
어려운 문제에서는 $3 \le N \le 10^{12}$인 입력이 주어진다.
출력 형식
첫 번째 줄에 형석이가 연결하게 될 철사의 개수를 출력한다.
예제 1
입력
3
출력
1
예제 2
입력
4
출력
3
예제 3
입력
5
출력
2
Problem Source