8

我想确定阶乘的最后一个非零数字。

我尝试使用除法来解决它：将数字除以 10 或其倍数。

Ex : 7! = 5040 => 4

所以我将 5040 除以 10 得到 4 作为结果。

但是，让我们说，我们应该在逻辑中使用数字 7 而不是阶乘 (5040) 的值。

请让我知道我该怎么做？

4

3 回答 3

13
  1. 计算 n! 的素数分解！如下：
    • 对于每个素数p<= n， p 的指数是
  2. 从素数分解的指数中减去指数5并2丢弃所有的五。
  3. 将剩余的素数分解模 10 相乘。注意，这样做时，您可以使用以下等式：（对于 i ≥ 0）。如有必要，也可以对单个产品进行 mod 10。

我利用一些空闲时间在 bash 中实现了这个解决方案。（bash？好吧，为什么不呢？）：

last_nonzero () { 
    local n=$1
    local d=$(power_mod_10 3 $(count_factors $n 3))
    d=$((d * $(power_mod_10 2 $(($(count_factors $n 2)
                               - $(count_factors $n 5))))))
    for p in $(primes 7 $n)
    do
        d=$((d * $(power_mod_10 $p $(count_factors $n $p)) % 10))
    done
    echo $d
}

count_factors () { 
    local n=$1 p=$2
    local d=$((n/p))
    local q=$d
    while ((q >= p)); do
        q=$((q/p)) d=$((d+q))
    done
    echo $d
}

power_mod_10 () { 
    local mods=..........0161000101012300070901490009010187000309
    local p=$(($1%10)) exp=$(($2%4+1))
    echo ${mods:$exp$p:1}
}

是的，最后一个是hack。

另外：还有一个更好的递归解决方案。搜索http://math.stackexchange.com，甚至 google。

于 2012-11-02T14:21:51.877 回答
1

假设 D(N) 表示阶乘的最后一个非零数字，那么

D(N)=4*D[N/5]*D(N的个位)[如果N的十位为奇数] D(N)=6*D[N/5]*D(N的个位)[如果N的十位是偶数]; 其中 [N/5] 是最大整数函数并且 D(1)=1 D(2)=2 D(3)=6 D(4)=4 D(5)=2 D(6)=2 D(7 )=4 D(8)=2 D(9)=8

例如 D(26)=6*D[26/5]*D(6)=6*D(5)*D(6)=6*2*2=4[D(5) 表示最后一个非零位5!=120 即 2，与 D(6) 相同] D(33)=4*D[33/5]*D(3)=4*D(6)*D(3)=4*2* 6=8

参考：http: //quantomania.blogspot.in/2011/08/last-non-zero-digit-of-factorial.html

于 2013-07-16T16:42:17.480 回答
1

当下一个（修改的）数字以 5 结尾时，需要保留1 个以上的数字。

第一个这样的位置出现在 15！，当 14！= 87178291200 和 2*15=30 但 15！= 1307674368000。而是 12*15 = 180，这给出了正确的结果。

编辑：但即使将数字加到 2 也不足以满足 25 的一般情况！一个需要 24 的最后 3 位数字！= 936 才能得到正确答案，这意味着最终这种方法经不起推敲。

于 2012-11-02T13:51:28.280 回答