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\)的数的个数，可以做分类讨论：

• 当\(n=1\)时，显然\(H(1,f)=1\)；
• 当\(f=2\)时，即最大质因数为\(2\)的数的个数，则这些数只能是1以及2的幂，则这样的数的个数应为\(\lfloor log_{2}( n)\rfloor +1\)个；
• 当\(n<f\)时，显然有\(H(n,f)=H(n,n)\)；
• 当\(f\) 是一个合数时，则\(H(n,f)=H(n,f-1)\)；
• 当\(f\)是一个质数时，\(n\)以内的\(f\)汉明数可以分为两类，一类是最大质因数不超过\(f-1\)的数，它们的个数为\(H(n,f-1)\)；另一类是最大质因数为\(f\)的数，它们的个数等于\(n\)以内的\(f\)的倍数中最大质因数不超过\(f\)的数的个数，即\(H(n/f,f)\)。

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

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

# 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)