124. 根基排序(Ordered radicals)

\(n\)的根基指\(n\)的不同质因数的乘积,也记作\(rad(n)\)。例如:

$$ 504=2^3\times3^2\times7\Rightarrow rad(504)=2\times3\times7=42 $$
\(1\le n\le10\)时我们计算\(rad(n)\),然后根据\(rad(n)\)把结果升序排列,如果\(rad(n)\)相同再根据数\(n\)排序,我们可以得到:

img

\(E(k)\)为排序后的\(n\)列中的第\(k\)个元素,例如\(E(4)=8,E(6)=9\)。对\(1\le n \le100000\)\(rad(n)\)进行排序,求\(E(10000)\)

分析:这道题的思路相对直接,只需要把范围内的数\(n\)的根基\(rad(n)\)求出来然后升序排列,如果两个数的\(rad(n)\)相同,再根据\(n\)的大小来排序。排序完成后,输出第一万个\(rad(n)\)对应的\(n\)的值即可。所以主要问题有两个,一是如何求出范围内的\(rad(n)\),二是如何按照题目的要求对其进行排序。

对于第一个问题,我们当然可以依次求出每个数的\(rad(n)\),但是这种方法要求对每个数\(n\)进行质因数分解,然后计算它们的乘积,当涉及的数据规模较大时,效率会比较低。一个更高效的方法是使用筛法的思想,将每个数\(n\)的质因数累乘,最终得到的就是这个数的\(rad(n)\)。这里的思路和我们使用埃拉托斯特尼筛法筛选特定范围内的质数是类似的,就不详细介绍了,看代码很容易理解。

对于第二个问题,我们需要考虑题目的特殊要求,也就是在\(rad(n)\)相同的时候按\(n\)的大小排序,为了实现这种排序模式,我们可以采用一个嵌套的列表。一个大列表中包含若干小列表,每个小列表包含两个元素,第一个元素是\(rad(n)\),第二个元素是\(n\),当对整个大列表进行排序时,\(python\)会先根据第一个元素也就是\(rad(n)\)排序,当第一个元素相同时再根据第二个元素也就是数\(n\)排序,正是题目要求的排序模式。代码如下:

# time cost = 153 ms ± 1.19 ms

def main(n=10**5,k=10**4):
    arr = [[1,i] for i in range(n+1)]
    for i in range(2,n+1):
        if arr[i][0] == 1:
            for j in range(i,n+1,i):
                arr[j][0] *= i
    return sorted(arr)[k][1]