Last active
February 12, 2018 15:15
-
-
Save AnthonyMikh/1929e9f145e1ae764dff75932b559a40 to your computer and use it in GitHub Desktop.
Решение задачи №69 от UniLecs
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Data.Word (Word64) | |
power5 = iterate (*5) 5 | |
factorialZeroes n = sum . takeWhile (/=0) . zipWith (flip div) power5' . repeat $ n | |
where | |
takeWhilePlusOne cond x = | |
let (first, s:econd) = span cond x | |
in first ++ [s] | |
power5' = takeWhilePlusOne (<= (n `div` 5)) power5 | |
main = print . factorialZeroes $ (100 :: Word64) |
Обоснование:
Для того, чтобы число оканчивалось на 0, требуется, чтобы его делителем было число 10 = 2 * 5. Так как, как несложно показать, среди чисел от одного до n
кратных 2 больше, чем кратных пяти, полная степень десятки в разложении n!
ограничивается числом кратных 5 чисел, не превосходящих n
, число которых -- целое от частного n
и 5.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Playground: https://repl.it/repls/AmusedBonyActivecell