방정식
시간 제한2초메모리 제한128 MB
N이 주어질 때 X+Y=Z, X<=Y를 만족하는 경우의 수를 서로 다른 정수 조건, N의 약수 조건, N 이하 소수 조건 각각에 대해 구합니다.
문제
세 자연수 (X), (Y), (Z)가 다음 방정식을 만족한다고 하자.
[ X + Y = Z \quad (X \le Y) ]
제약 조건이 없다면 해는 무수히 많다. 아래 세 조건을 각각 독립적으로 적용했을 때, 방정식을 만족하는 해의 개수를 구하라.
- 제약 조건 A: (X), (Y), (Z)는 모두 (N) 이하이고, 서로 다르다.
- 제약 조건 B: (X), (Y), (Z)는 모두 (N)의 양의 약수이다.
- 제약 조건 C: (X), (Y), (Z)는 모두 (N) 이하의 양의 소수이다.
각 조건은 동시에 적용되지 않는다. 조건 A, B, C 각각에 대해 가능한 해의 개수를 따로 계산한다.
입력
첫째 줄에 자연수 (N)이 주어진다.
[ 1 \le N \le 500,000 ]
출력
첫째 줄에 제약 조건 A에서의 해의 개수를 출력한다.
둘째 줄에 제약 조건 B에서의 해의 개수를 출력한다.
셋째 줄에 제약 조건 C에서의 해의 개수를 출력한다.