求正整数n的约数中不大于给定正整数k的有多少个，n的质因数分解已知
给定正整数及其因数分解标准形式\(\D n=\prod_{i=1}^m p_i^{a_i}\)。求\(n\)的约数中所有不大于给定正整数\(k\)的约数的数量。
姑且记作\(F(n,k)\)吧。 取对数就变成线性不等式。 递归化简吧
设数字是n，$p^t|n$而$p^{t+1}\not |n$
现在计算有多少个n中能被p整除而不大于k的约数个数
在算出这个数字之后，考察$\frac n{p^t}$与$\frac k{p^t}$，我们会发现，n中每一个不大于k且不能被p整除的约数都与$\frac n{p^t}$中不大于$\left[\frac k{p^t}\right]$的约数一一对应，由此我们可以将问题化简。
对于“n中能被p整除而不大于k的约数个数”这个问题
首先计算n/p跟k/p，如果某个能被p整除的约数$d\le k$，那么$\frac dp\le \frac kp$
于是问题可以进一步转化成，对整数$\frac np$，计算$\frac np$的约数中所有不大于给定正整数$\left[\frac kp\right]$的约数的数量。
然后就可以递归化简/动态规划了
页:
[1]