시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 128 MB | 300 | 131 | 81 | 41.538% |
안암골짜기에는 ALPS(Anam Lotated Pill Station) 라는 이름의 유명한 제약회사가 있다. 그곳이 유명한 이유는, 그 회사가 제조하는 모든 약은 오로지 "소주"와 "맥주" 두 가지 재료를 통해서만 만들어지기 때문이다. ALPS의 사장 재헌은 소주와 맥주를 적절히 섞음으로써 모든 병을 치료할 수 있다는 믿음 하에 약을 팔고있다.
새해를 맞이하여 약을 거하기 마신 사장 재헌은 회사에 다음과 같은 신년계획을 지시했다.
ALPS 회사 직원들 모두 약을 거하게 마셨기 때문에 이 지령에 대해 불만을 가지지 않고 잘 따르기로 하였다.
어느 날, 회사의 신묘한 약의 기운을 원하는 손님 홍준이 회사에 찾아와서 "정제헌"을 요구하였다. ("정제헌"은 ALPS에서 자랑하는, 잘 정제된 약이다.) ALPS의 신년계획에 의해서 모든 약은 자연수의 역수 꼴의 비커에 가득 담겨져있다. "정제헌" 또한 1/n 비커에 가득 담겨져있는 상태다.
ALPS 사장 재헌은 홍준에게 "정제헌" 1/n 을 전부 주고싶지 않다. 때문에 그는 "정제헌" 1/n 을 각각 1/x 와 1/y 의 용량을 가진 플라스크에 나눠담아서 1/x 에 담긴 "정제헌"을 홍준에게 주고 1/y 는 회사에 남기기로 하였다. 그런데 아차! 1/x 플라스크는 판매용이고, 1/y 플라스크는 보관용이다. 신년계획에 의해 1/x 플라스크와 1/y 플라스크 모두에 "정제헌"이 가득 담겨져 있어야 한다는 뜻이다!
재헌은 1/x 플라스크와 1/y 플라스크를 고르는 도중 문득 (팔라는 약은 안팔고) 신년계획을 지키면서 "정제헌"을 두 플라스크에 나눠담는 경우의 수가 궁금해졌다. 재헌이의 궁금증을 빠르게 해결하고, 홍준이에게 "정제헌"을 무사히 팔 수 있도록 도와주자.
각 줄마다 테스트 케이스가 주어진다.
각 테스트 케이스는 한줄로 "정제헌"의 용량이 "1/n" 형태로 주어진다. 1 ≤ n ≤ 10 000. 을 만족하며, 입력으로 공백이 들어오지 않는다고 가정한다.
각 케이스마다 한 줄씩 "정제헌"을 플라스크에 나눠담을 수 있는 경우의 수를 출력한다. 즉, 1/x+ 1/y = 1/n 을 만족하는 자연수 {x,y} 쌍의 가지수를 출력한다. 두 플라스크 중 하나는 판매용이기 때문에, {x,y} 와 {y,x} 는 서로 다른 경우가 아니다.
1/2 1/4 1/1 1/5000
2 3 1 32
ICPC > Regionals > Europe > Central European Regional Contest > CTU Open Contest > CTU Open Contest 2013 L번