ABC 추측

위키백과에서 가져온 설명입니다:

abc 추측(Oesterlé-Masser 추측이라고도 한다)은 Joseph Oesterlé(1988)과 David Masser(1985)가 처음 제시한 수론의 추측이다. 서로소인 세 양의 정수 $a$, $b$, $c$로 표현하며(이름이 여기서 왔다), $a + b = c$를 만족한다. $d$를 $a \cdot b \cdot c$에 나타나는 서로 다른 소인수의 곱이라 하면, 이 추측은 대체로 $d$가 $c$보다 그리 작지 않다고 말한다. 달리 말해, $a$와 $b$가 큰 거듭제곱 소수로 이루어져 있으면 $c$는 보통 큰 거듭제곱 소수로 나누어떨어지지 않는다.

abc 추측은 그로부터 따라 나오는 흥미로운 결과가 많은 것으로 잘 알려져 있다. 수론의 유명한 추측과 정리 가운데 여럿이 이 추측에서 바로 따라 나온다. Goldfeld(1996)는 abc 추측을 "디오판토스 해석에서 가장 중요한 미해결 문제"라고 평했다.

이 추측에 대한 해법은 여러 개 제시되었다. 그중 가장 최근의 해법은 아직도 수학계에서 검토 중이다.

용어를 단순하게 정리하면 다음과 같다.

• $a$, $b$, $c$는 양의 정수이다.
• $a$, $b$, $c$는 각각 서로 다른 소인수로 이루어져 있다.

용어를 보이기 위해 $a = 16 = 2^4$, $b = 17$, $c = 16 + 17 = 33 = 3 \cdot 11$이라고 하자. 그러면 $d = 2 \cdot 17 \cdot 3 \cdot 11 = 1122$이고, 이는 $c$보다 크다.

이 문제의 목표는 주어진 $a$, $b$, $c$의 범위에서 $c > d$인 예외를 찾는 것이다.

첫째 줄에 테스트 케이스의 개수 $N$($0 < N < 100$)이 주어진다.

이어지는 $N$개의 줄에는 각각 두 정수 $L$과 $H$($2 \le L \le H \le 5000$)가 주어진다. 이들은 $a$, $b$, $c$의 하한과 상한이다. 조건은 $L \le a, b < c \le H$이며 $a \ne b$이다.

각 테스트 케이스에 대해 다음 중 하나를 출력한다.

• 위 조건을 만족하는 등식마다 "$a + b = c$" 형태의 줄을 출력한다. 줄은 $c$의 오름차순으로 정렬하고, $c$가 같으면 $a$의 오름차순으로 정렬한다.
• 조건을 만족하는 등식이 없으면 "No exceptions"를 출력한다.

각 테스트 케이스의 출력 뒤에는 빈 줄을 하나 출력한다.