标签：prime code smoothnumber 记录 number 然后

[ABC300G] P-smooth number

上来看到题就可以爆搜了。状态是 \(f[p][n]\) 表示现在再在处理第 \(p\) 小的素数，剩余 \(n\)。然后转移是 \(f[n][p]=f[n/prime[p]][p]+f[n][p-1]\)，分别表示除掉一个 \(prime\)，转到下一个 \(prime\)，这样做显然是对的，因为如果一个数在范围内，那么这样除只要最后不是 \(1\) 一下，那么乘起来必然是在 \(N\) 内。

然后考虑优化。这个有点像 DP，然后想到可以记录状态，但是不能全部记录，可以记录 \(2^{16}\) 以内的 \(n\)，然后就神奇的过了。

code

标签：prime,code,smoothnumber,记录,number,然后
From： https://www.cnblogs.com/wscqwq/p/17488687.html