siz*_*erz 6 algorithm math numbers
是否有一种有效的算法来计算最小整数N,使得N!可以被p ^ k整除,其中p是一个相对较小的素数,k是一个非常大的整数.换一种说法,
factorial(N) mod p^k == 0
如果给定N和p,我想找到p分成N!的次数,我会使用众所周知的公式
k = Sum(floor(N/p^i) for i=1,2,...
我已经对k的小值进行了强力搜索,但随着k的增加,这种方法很快就会崩溃,并且似乎没有一种模式可以推断为更大的值.
2011年6月13日编辑
使用Fiver和Hammar提出的建议,我使用准二分搜索来解决问题但不完全按照他们的建议.使用上面第二个公式的截断版本,我计算了N的上限作为k和p的乘积(仅使用第一项).我用1作为下限.使用经典二进制搜索算法,我计算了这两个值之间的中点,并计算了在第二个公式中使用此中点值作为N的k,这次使用了所有项.
如果计算的k太小,我调整下限并重复.太大了,我首先测试看中间点1计算的k是否小于期望的k.如果是这样,中点返回为最接近的N.否则,我调整了高点并重复.
如果计算的k相等,我测试了中点-1处的值是否等于中点处的值.如果是这样,我将高点调整为中点并重复.如果中点-1小于期望的k,则返回中点作为期望的答案.
即使k值非常大(10位或更多位),这种方法也可以使用O(n log(n))速度.
k使用您提到的公式，给出的值序列是固定的p并且N = 1,2...是非递减的。这意味着您可以使用二分搜索的变体来查找N给定的所需的k.
N = 1，然后计算k。N直到k大于或等于您想要k获得的上限。k.