204. 广义汉明数(Generalised Hamming Numbers)

若一个正整数的所有质因数均不超过5,则被称为汉明数。前几个汉明数分别是1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15。在不超过\(10^8\)的正整数中,一共有1105个汉明数。若一个正整数的所有质因数均不超过\(n\),则被称为\(n\)型广义汉明数,因此本来的汉明数就是五型广义汉明数。求在不超过\(10^9\)的正整数中,一共有多少个\(100\)型广义汉明数?

分析:我们可以借用筛法的思路使用动态规划的方法来解决这个问题,比如说我们要求15以内的五型汉明数个数,我们可以这些数分为两类,一类是最大质因数不超过三的数,这包括1,2,3,4,6,8,9,12总共八个数;另一类则是最大质因数为五的数,这包括5,10,15三个数,所以总共是十一个数。

对于广义汉明数,思路也是类似的,设\(H(n,f)\)表示\(n\)以内的最大质因数不超过\(f\)的数的个数,可以做分类讨论:

综上,我们可以得到状态转移方程如下:

$$ H( n,f) =\begin{cases} 1 & n=1\\ \lfloor log_{2}( n)\rfloor +1 & f=2\\ H( n,n) & n< f\\ H( n,f-1) & f\ is\ not\ prime\\ H( n,f-1) +H( n/f,f) & else \end{cases} $$

根据以上状态转移方程,我们可以容易写出动态规划的代码如下:

# time cost = 103 ns ± 3.11 ns

from math import log
from sympy import isprime
from functools import lru_cache

@lru_cache(maxsize=None)
def hn(n,f):
    if n == 1:
        return 1
    elif f == 2:
        return int(log(n,2))+1
    elif n < f:
        return hn(n,n)
    elif not isprime(f):
        return hn(n,f-1)
    else:
        return hn(n,f-1)+hn(n//f,f)

def main(n=10**9,f=100):
    return hn(n,f)