约数的数量是2的幂，因此该数的质因数分解一定具有$p_1^{2^{e_1}-1}\ldots p_k^{2^{e_k}-1}$的形式。
所以找出足够多的素数，依次生成其符合条件的幂，并用一个堆来控制添加符合要求的数即可。
最终结果是$35407281$。
注：为减少码量，直接用sympy生成素数，因此以下代码为Python 3。
import sympy,heapq
N=500500
M=7376508
mod=500500507
q=[]
for p in sympy.primerange(M):
heapq.heappush(q,p)
res=1
for i in range(N):
x=heapq.heappop(q)
res=res*x%mod
heapq.heappush(q,x*x)
print(res)
|
