设A是自然数，若存在整数p、q、r满足： $$A=pqr \text{ 且 } \frac{1}{A}=\frac{1}{p}+\frac{1}{q}+\frac{1}{r},$$ 就称A是亚历山大数。

例如，630是亚历山大数（取$p=5, q=−7, r=−18$）。事实上630是第六个亚历山大数，前六个亚历山大数分别是6、42、120、156、420和630。

求第150000个亚历山大数。

本题难度:

解答

根据OEIS A147811的信息，A可以由如下公式生成： $$A=p(p+d)(p+\frac{p^2+1}{d}),$$ 其中p取遍所有自然数，d取遍$p^2+1$的约数。

用与第216题类似的筛法作$p^2+1$的质因数分解，然后遍历p（p的上限经过尝试取为80000），用$p^2+1$的质因数分解枚举其所有约数。

生成的亚历山大数加入集合去重，最后排序即得结果$1884161251122450$。

注：以下为Python 3代码，因math.prod是Python 3中新增的函数，用星号作列表展开也是Python 3的新特性。

import math,itertools

bound=80000
f=[i*i+1 for i in range(bound)]
g=[{} for i in range(bound)]

for i in range(1,bound):
    if f[i]>1:
        p=f[i]
        for j in range(i,bound,p):
            while f[j]%p==0:
                f[j]//=p
                g[j][p]=g[j].get(p,0)+1
        for j in range(p-i,bound,p):
            while f[j]%p==0:
                f[j]//=p
                g[j][p]=g[j].get(p,0)+1

a=set()
for p in range(1,bound):
    r=list(g[p].keys())
    for d in [math.prod(r[i]**j for i,j in enumerate(c)) for c in itertools.product(*[range(g[p][k]+1) for k in r])]:
        a.add(p*(p+d)*(p+(p*p+1)//d))

print(sorted(a)[149999])