x, y, n이 모두 자연수인 다음 방정식이 있습니다.

1 x

+

1 y

=

1 n

n=1260일 때 위 방정식을 만족하는 (x, y) 해는 총 113개가 있습니다. 1260은 (x, y) 해의 쌍이 100개를 넘는 가장 작은 n입니다.

(x, y) 해의 쌍이 4,000,000개를 넘는 가장 작은 n은 얼마입니까?

주) 이 문제는 108번 문제의 업그레이드 버전입니다. 짐승력으로 문제를 풀기에는 무리가 있으므로 좀 더 효율적인 방법을 고민해 보세요.