Project Euler 500

题目

Problem \(500\)!!!

The number of divisors of \(120\) is \(16\).

In fact \(120\) is the smallest number having \(16\) divisors.

Find the smallest number with \(2^{500500}\) divisors.

Give your answer modulo \(500500507\).

解决方案

注意到，所求的数的除数是一个二次幂（\(2^{N},N=500500\)）,那么所求的这个数一定是形如这种形式：

\[2^{2^{e_1}-1}\times3^{2^{e_2}-1}\times 5^{2^{e_3}-1}\times \dots\]

如果要令一个数\(n\)的因子数翻倍，观察\(n\)的因数个数公式\(\prod (e_i+1)\)，有以下两个操作办法：

• 为\(n\)乘上一个\(n\)中还未存在的质因数，这相当于添加了一个新的项\((1+1)\)。
• \(n\)的分解质因数中，假设其中一项为\(p_i^{e_i}\)，那么就为\(n\)乘上\(p_i^{e_i+1}\)，这相当于把项\((e_i+1)\)变成了\((2e_i+2)\)。另外，如果当前对应质因子\(p_i\)的一项是\(x\)，那么下一次待添加的就是\(x^2\)。

因此，使用优先队列维护这些等待被\(n\)相乘的数，找出最小的一个为\(n\)乘上即可，过程迭代\(N\)次。

代码

from tools import get_prime
from queue import PriorityQueue

M = 500500
mod = 500500507
pr = get_prime(M * int(len(bin(M)) - 2) + 14)
N = M * int(len(bin(M)) - 2)
q = PriorityQueue()
for i in range(M):
    q.put(pr[i])
ans = 1
for i in range(M):
    x = q.get()
    ans = ans * x % mod
    q.put(x * x)
print(ans)