algorithm - 阶乘的最后一个非零数字

Question

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

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

Ex : 7! = 5040 => 4

所以我将 5040 除以 10 得到 4。

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

请告诉我该怎么做？

Answer 1

1. 计算 n 的质数分解!如下:
   • 对于每个质数 p <= n，p 的指数是
     
2. 从 2 的指数中减去 5 的指数，并丢弃素数分解中的所有五。
3. 将剩余的质数分解模 10 相乘。请注意，执行此操作时，您可以使用以下等效项: (对于 i ≥ 0)。如有必要，也可以对单个产品进行模数 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 ，甚至谷歌。