정사각형

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

요약

자연수 N이 주어질 때, a+b-gcd(a,b)가 N이 되는 순서 없는 정수 변 쌍 (a,b)의 개수를 구하는 문제입니다.

문제

$R$ 은 각 변의 길이가 정수인 직사각형이다. 이 직사각형은 한 변의 길이가 $1$ 인 단위 정사각형들로 빈틈없이 나눌 수 있다.

$f(R)$ 을 직사각형 $R$ 의 한 대각선이 지나가는 단위 정사각형의 개수라고 정의한다. 예를 들어 두 변의 길이가 $2$ 와 $4$ 인 직사각형은 $f(R) = 4$ 이다.

자연수 $N$ 이 주어졌을 때, $f(R) = N$ 을 만족하는 직사각형 $R$ 의 개수를 구하여라. 단, 두 변의 길이가 $a$ , $b$ 인 직사각형과 $b$ , $a$ 인 직사각형은 같은 직사각형으로 본다.

첫째 줄에 자연수 $N$ ( $0 < N < 10^6$ )이 주어진다.

첫째 줄에 $f(R) = N$ 을 만족하는 직사각형 $R$ 의 개수를 출력한다.

$a \times b$ 직사각형의 대각선이 지나가는 단위 정사각형의 개수를 두 변의 길이 $a$ 와 $b$ 만으로 어떻게 나타낼 수 있을지 생각해 보아라.