Skip to content

Instantly share code, notes, and snippets.

@AnthonyMikh
Last active February 12, 2018 15:15
Show Gist options
  • Save AnthonyMikh/1929e9f145e1ae764dff75932b559a40 to your computer and use it in GitHub Desktop.
Save AnthonyMikh/1929e9f145e1ae764dff75932b559a40 to your computer and use it in GitHub Desktop.
Решение задачи №69 от UniLecs
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)
@AnthonyMikh
Copy link
Author

AnthonyMikh commented Feb 11, 2018

@AnthonyMikh
Copy link
Author

AnthonyMikh commented Feb 11, 2018

Обоснование:
Для того, чтобы число оканчивалось на 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