Lintcode 2の末尾の0
1924 ワード
1、テーマ
テキストリンク:http://www.lintcode.com/zh-cn/problem/trailing-zeros/
説明: n次乗における末尾ゼロの個数を計算するアルゴリズムを設計した.
サンプル: 11! = 39916800なので、2を返すべきです.
2、分析
もしあなたが1× 2 ×３× 4 ×……×Nの各因数は質量因数を分解し,結果は次のようになった.× 2 × 3 × (2 × 2) × 5 × (2 × 3) × 7 × (2 × 2 ×2) ×…… 10進数の末尾の各0は、1つの因数10が存在することを示す.いずれの進数も同じであり、1つのM進数の数に対して、末尾の1つ以上の0をMに乗じることに等価にする.10は2に分解できる× 5-したがって、素数2と5の乗算だけが0を生成することができ、他の2つの素数の乗算は0を生成することができず、2、5の乗算は1つの0しか生成されません.したがって,分解後の全因数式には何対(2,5)があり,結果には何個の0があり,分解の結果,2の個数は明らかに5より多いので,何個の5があり,何個の(2,5)対があるかである.したがって,1000の階乗終端にいくつかの0があるという問題を議論すると,これらの数のすべての素因数分解式がどれだけ5があるかという問題に変換される.
シーケンス1、2、3、4、5、6、7、8、9、10、11、...
上の数の列を分析すると、5つの数に1つの結果の0を生成できる数字が表示されます.これらの数字を抽出すると、
…、5、…、10、…、15、…、20、…、25、…
これらの数字は実はすべて5*kの数字を満たすことができて、5の倍数です.彼らの数を統計してみます:n 1=N/5.例えば101であれば、101の前に5,10,15,20,...,95100の101/5=20の数字が要求を満たすはずです.
除去操作は上記の数量統計要求を満たす.
1の中のこれらを5*(1、2、3、4、5、...)の形式にデジタル化して、内部の1、2、3、4、5、...はまた上の分析を満たします:5つの数字ごとに1つは5の倍数です.抽出:
…、25、…、50、…、75、…、100、…、125、…
これらの数字はすべて25の倍数(5の2乗の倍数)で、自然もすべて5*kの要求を満たします. これらの数字は25,50,75,100,125,…=5*(5,10,15,20,25,…)=5*5*(1,2,3,4,5,…)であり、内部の1,2,3,4,5,…は上記の分析を満たしているので、後続の操作は上記の手順を繰り返すとよい.
2回目の条件を満たす数字の数を統計します:n 2=N/5/5101/25=(101/5)/5=4.
25、50、75、100、125、・・これらはいずれも乗算を満たした後に少なくとも2つの0を生成するため、第1の5*k分析で1回統計された.N=101の場合、20です.したがって,ここでの5*5*kは1回4を統計すればよく,25が5の二次べき乗に基づいて2回統計する必要はない.
後の125250、...などの積が1000の結果に3つの0を貢献できる数字は、5*5*kに基づいてn 3=(((N/5)/5)/5をもう一度統計すればよい.
コアポイント:末尾のゼロは5の個数で決定され、単5(因式分解後に1つの5)はある偶数に単0を乗算し、多5(因式分解後に複数の5)はある偶数に複数の0を乗算する.
3、ACコード
テキストリンク:http://www.lintcode.com/zh-cn/problem/trailing-zeros/
説明: n次乗における末尾ゼロの個数を計算するアルゴリズムを設計した.
サンプル: 11! = 39916800なので、2を返すべきです.
2、分析
もしあなたが1× 2 ×３× 4 ×……×Nの各因数は質量因数を分解し,結果は次のようになった.× 2 × 3 × (2 × 2) × 5 × (2 × 3) × 7 × (2 × 2 ×2) ×…… 10進数の末尾の各0は、1つの因数10が存在することを示す.いずれの進数も同じであり、1つのM進数の数に対して、末尾の1つ以上の0をMに乗じることに等価にする.10は2に分解できる× 5-したがって、素数2と5の乗算だけが0を生成することができ、他の2つの素数の乗算は0を生成することができず、2、5の乗算は1つの0しか生成されません.したがって,分解後の全因数式には何対(2,5)があり,結果には何個の0があり,分解の結果,2の個数は明らかに5より多いので,何個の5があり,何個の(2,5)対があるかである.したがって,1000の階乗終端にいくつかの0があるという問題を議論すると,これらの数のすべての素因数分解式がどれだけ5があるかという問題に変換される.
シーケンス1、2、3、4、5、6、7、8、9、10、11、...
上の数の列を分析すると、5つの数に1つの結果の0を生成できる数字が表示されます.これらの数字を抽出すると、
…、5、…、10、…、15、…、20、…、25、…
これらの数字は実はすべて5*kの数字を満たすことができて、5の倍数です.彼らの数を統計してみます:n 1=N/5.例えば101であれば、101の前に5,10,15,20,...,95100の101/5=20の数字が要求を満たすはずです.
除去操作は上記の数量統計要求を満たす.
1の中のこれらを5*(1、2、3、4、5、...)の形式にデジタル化して、内部の1、2、3、4、5、...はまた上の分析を満たします:5つの数字ごとに1つは5の倍数です.抽出:
…、25、…、50、…、75、…、100、…、125、…
これらの数字はすべて25の倍数(5の2乗の倍数)で、自然もすべて5*kの要求を満たします. これらの数字は25,50,75,100,125,…=5*(5,10,15,20,25,…)=5*5*(1,2,3,4,5,…)であり、内部の1,2,3,4,5,…は上記の分析を満たしているので、後続の操作は上記の手順を繰り返すとよい.
2回目の条件を満たす数字の数を統計します:n 2=N/5/5101/25=(101/5)/5=4.
25、50、75、100、125、・・これらはいずれも乗算を満たした後に少なくとも2つの0を生成するため、第1の5*k分析で1回統計された.N=101の場合、20です.したがって,ここでの5*5*kは1回4を統計すればよく,25が5の二次べき乗に基づいて2回統計する必要はない.
後の125250、...などの積が1000の結果に3つの0を貢献できる数字は、5*5*kに基づいてn 3=(((N/5)/5)/5をもう一度統計すればよい.
コアポイント:末尾のゼロは5の個数で決定され、単5(因式分解後に1つの5)はある偶数に単0を乗算し、多5(因式分解後に複数の5)はある偶数に複数の0を乗算する.
3、ACコード
class Solution:
"""
@param: n: An integer
@return: An integer, denote the number of trailing zeros in n!
"""
def trailingZeros(self, n):
# write your code here, try to do it without arithmetic operators.
sum = 0
while n > 0:
sum += n /5
n /= 5
return sum