110. 丢番图倒数二(Diophantine reciprocals II)
在以下方程中，\(x,y,n\)都是正整数：
$$ \dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n} $$可以验证当\(n=1260\)时上述方程恰好有\(113\)个不同的正整数解，这是该方程不同的正整数解的个数超过一百时\(n\)的最小值。求不同的解的总数超过四百万时的最小的\(n\)值是多少？注：这个问题是比\(problem\ 108\)的困难的多的版本，由于它已经远远超出了暴力方法的极限，因此需要一个更为巧妙的方法。
分析：在\(problem\ 108\)中，我们已经对这个问题进行了详细分析，这道题的唯一区别是数据规模更大，无法用暴力方法解决，但是可以用我们在\(problem\ 108\)中展示的方法在较短时间内解决。关于方法的原理，我这里不再赘述，具体大家可以参见第一百零八题的分析。代码如下：
# time cost = 1.41 s ± 9.52 ms
from sympy import factorint
from functools import reduce
from operator import mul,add
def prime_product(factors):
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
powers = sorted(reduce(add,[[(k-1)//2]*v for k,v in factors.items()]),reverse=True)
bases = primes[:len(powers)]
res = reduce(mul,[b**p for b,p in zip(bases,powers)])
return res
def main(N=4*10**6):
n = 2*N - 1
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
while True:
factors = factorint(n)
if all(x in [3,5,7] for x in factors.keys()):
return prime_product(factors)
n += 2