算是 OI 弱相关的东西(?
因为见到了好几个可以这么嗯搞的东西,所以发出来看看。
3-smooth 数
如果一个正整数的所有素因子均不大于 \(3\),我们称之为 3-smooth 数。
容易发现,3-smooth 数的一个等价定义就是能表示成 \(2^x3^y\) 的数,其中 \(x,y\in\mathbb N\)。
你可以在 OEIS A003586 中看到若干 3-smooth 数,以及相关的近似级别等信息。这里摘录其的前若干项:\(1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,64,72,81,96\)。
对于任意一个正整数 \(n\),其总可以分解成 \(2^x3^yz\) 的形式,其中 \(2\nmid z\land3\nmid z\),也即可以分解成一个 3-smooth 数乘上 \(z\),其中 \(z\bmod6\in\{1,5\}\)。
这样我们就可以以 \(z\) 为代表元来划分等价类了。
即,当我们要考察 \(\le n\) 的所有正整数时,我们可以枚举 \(z\),然后对剩余部分的 3-smooth 数进行考虑,容易发现也就是 \(\lfloor n/z\rfloor\) 内的所有 3-smooth 数。
当要考察 \(\le n\) 的所有 3-smooth 数时,我们可以把其画成 Young 表的形式来考虑。
即,注意到当 \(y\) 增加 \(1\) 时,可能最大的 \(x\) 必定会恰好减少 \(1\) 或者 \(2\)。
譬如,如果我们要考察 \(\le100\) 的所有 3-smooth 数,可以画成这样的形式:
\[\begin{matrix}1&2&4&8&16&32&64\\3&6&12&24&48&96\\9&18&36&72\\27&54\\81\end{matrix} \]也就是前面所摘录的那些项。
容易发现使用这个形式我们就可以估计 \(\le n\) 的 3-smooth 数的数目级别了。毛估估大概就是 \(\frac{\ln^2n}{2\ln2\ln3}+O(1)\) 的样子。
例题
因为实在没啥知识点,直接丢例题了。
bzoj2734 [HNOI2012]集合选数
枚举 \(z\),直接对着 Young 表的一列状压就完了。
复杂度是容易分析的。
SPOJ SUMMING
神秘题,可以看这篇题解。
题解里给出了对第 \(n\) 项求取的一个不错的近似。
八校联考题 约树
这道题目就把上面那个 Young 表的作用体现得淋漓尽致了。
题解:【数据删除】
啥时候那题公开了再补吧。
标签:le,正整数,题解,可以,smooth,Young,相关 From: https://www.cnblogs.com/myee/p/3-smooth-number.html