철사 잇기

시간 제한1초메모리 제한256 MB

요약

원을 따라 일정한 간격으로 놓인 N개의 못을 삼각수만큼 이동하며 연결할 때 생기는 서로 다른 전선의 개수를 구합니다.

문제

큰 원의 둘레에 못 $N$ 개를 같은 간격으로 박았다. 그중 한 못을 $P_0$ 이라 하고, 거기서 시계 방향으로 나머지 못에 차례로 $P_1$ 부터 $P_{N-1}$ 까지 이름을 붙인다.

철사는 다음 규칙으로 잇는다.

$Q_0 = P_0$ 으로 둔다.
$p$ 단계를 $1$ 단계부터 $N^2$ 단계까지 반복한다. $Q_{p-1} = P_k$ 이면 $Q_p = P_{(k+p) \bmod N}$ 으로 정하고, $Q_{p-1}$ 과 $Q_p$ 를 철사로 잇는다. 두 못이 이미 이어져 있으면 새로 잇지 않는다. $Q_{p-1}$ 과 $Q_p$ 가 같은 못이면 잇지 않는다.

모든 단계를 마친 뒤 이어진 철사가 몇 개인지 구하라.

첫째 줄에 자연수 $N$ 이 주어진다. ( $3 \le N \le 10^{12}$ )

첫째 줄에 이어진 철사의 개수를 출력한다.