시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 300 | 103 | 74 | 30.833% |
알렉산드리아의 디오판토스는 알렉산드리아에 살던 이집트 수학자이다. 그는 정수로된 해 만을 가지는 다항 방정을 처음으로 연구한 수학자이다. 그를 기리기 위해서 후대에 이 방정식은 디오판토스 방정식이라고 이름이 붙었다.
가장 유명한 디오판토스 방정식은 \(x^n + y^n = z^n\)이다. 페르마는 \(n\) > 2인 경우에 정수해가 존재하지 않는다고 추론했고, 앤드루 와일스가 증명했다.
다음과 같은 디오판토스 방정식이 있다.
\(\frac{1}{x} + \frac{1}{y} = \frac{1}{n}\) where \(x,y,n \in \mathbb{N}^+\)
\(n\)이 주어졌을 때, 이 방정식의 해는 총 몇 개일까? (\(x\) ≤ \(y\)) \(n\) = 4인 경우에 아래와 같이 총 3가지 해가 존재한다.
\(\frac{1}{5} + \frac{1}{20} = \frac{1}{4}\) \(\frac{1}{6} + \frac{1}{12} = \frac{1}{4}\) \(\frac{1}{8} + \frac{1}{8} = \frac{1}{4}\)
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, \(n\)이 주어진다. (1 ≤ \(n\) ≤ 109)
각각의 테스트 케이스마다 "Scenario #i:"를 출력하고, 주어진 n에 대한 방정식의 해의 개수를 출력한다. 각 테스트 케이스 사이에는 빈 줄을 출력한다.
2 4 1260
Scenario #1: 3 Scenario #2: 113
University > Tu-Darmstadt Programming Contest > TUD Contest 2006 1번