algorithm - 階乗のゼロ以外の最後の桁

Question

階乗のゼロ以外の最後の桁を特定したい。

除算を使用して解決しようとしました: 数値を 10 またはその倍数で除算します。

Ex : 7! = 5040 => 4

したがって、5040 を 10 で割ると、結果として 4 が得られます。

しかし、階乗の値 (5040) の代わりに、ロジックで数字の 7 を使用する必要があるとしましょう。

どうすればよいか教えてください。

Answer 1

1. n の素数分解を計算してください! 次のように：
   • 各素数p<=nについて、p の指数は
     
2. 5の指数から の指数を引き、2素数分解から 5 をすべて破棄します。
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}
}

はい、最後のはハックです。

また、さらに優れた再帰的ソリューションがあります。http://math.stackexchange.com、またはグーグルで検索してください。

Answer 2

次の (変更された) 番号が 5 で終わる場合、複数の番号を保持する必要があります。

そのような最初の場所は 15! で、14! でした。= 87178291200、そして 2*15=30 でも 15! = 1307674368000。代わりに 12*15 = 180 となり、正しい結果が得られます。

編集:しかし、数字を2に追加しても、一般的なケースでは25では十分ではありません! 24 の最後の 3 桁が必要です。= 936 で正しい答えが得られます。つまり、結局、このアプローチは熱に耐えられないということです。