[ここ壊れてます] .net
>>286
pの倍数がn1個、p²の倍数がn2個、…とすると
n1+n2+…となる。
n1=[n/p]、n2=[n/p²]なので成り立つ。いずれ[n/p^k]=0となり以降0が続くことになる。
これを別の式で表す。
nをp進法で表して
n=(ak, a(k-1), …, a0) (p進法)
とk+1桁で表されたとすると
[n/p]=(ak, a(k-1), …, a1)
[n/p²]=(ak, a(k-1), …, a2)
となる。
よって(n-s)/(p-1)となる。
ここでnは元の数(10進数)、sはp進数表示における各位の和である。
100!は0が何個一の位から続くか
普通の解法
100/5=20、100/25=4より24個
公式を使った解法
100(10進法)=400(5進法)
(100-4)/4=24個
(n//k)が整数なのは組合せ論的な意味から明らか。これの別証を与える。
a=b+cとする。
(a//b)の分母に含まれる任意の素因数の個数を比較すると
Σ[a/p^k]≧Σ[b/b^k]+Σ[c/b^k]
なぜならば
右辺に切り捨てが無い場合は左辺にも切り捨てが無く、等号。
右辺の片方だけに切り捨て発生する場合も、等号。
右辺の両方に切り捨てが発生する場合にその切り捨て2個分で左辺では一個分取れる場合があり、不等号。
よって常に左辺は右辺以上となる。これから分母にある任意の素因数の個数について分子≧分母となり(a//b)は整数になる。