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