阶乘的最后一个非零数字

Question

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

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

Ex : 7! = 5040 => 4

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

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

请让我知道我该怎么办？

Answer 1

1. 计算n的素数分解!如下:
   • 对于每个素数p<= n,p的指数是
     
2. 5从指数中减去指数,2并丢弃主要分解中的所有五个.
3. 将剩余的素数分解模10乘以.注意,执行此操作时,可以使用以下等效项: (对于i≥0).如有必要,个别产品也可以通过mod 10完成.

我用了一些空余时间在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}
}

是的,最后一个是黑客.

另外:有一个更好的递归解决方案.搜索http://math.stackexchange.com,甚至谷歌.

Answer 2

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

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

编辑：但对于 25 的一般情况来说，即使将数字添加到 2 也是不够的！需要 24 的最后 3 位数字！= 936 得到正确答案，这意味着这种方法最终经不起考验。