Сравним степени вхождения двойки в и . В первом случае, очевидно, . Во втором: . Поэтому
3 votes Thanks 1
Guerrino
на примере 8 (здесь всего три двойки). Первая двойка считается в n/2 (здесь "снимается первый, нижний слой двоек). Вторая — в n/4 (второй слой), третья в n/8. попробуйте представить этот процесс в виде треугольника из точек, точно такого какой используется при геометрической интерпретации суммы 1+2+3+...+n
mathgenius
ant20202020, да если бы автору была интересна суть решения, то он бы уже участвовал в этой дискуссии еще до вас. А поскольку это не так, то ему/ей либо попросту неинтересно и он просто хочет списать и сдать решение, либо он все прекрасно понял и ему не нужно пояснений.
mathgenius
Guerrino все четко расписал и сослался в комментариях на формулу Лежандра. Лично я сам не слышал раньше о такой, я всегда считал степень вхождения простых чисел по своему алгоритму. Но вот теперь, благодаря Guerrino, я узнал самый эффективный способ.
mathgenius
Единственное, что наверное стоит сделать, сослаться на формулу Лежандра в самом решении. И написать, что сумма представляет собой геометрическую прогрессию. Ну и ,по желанию, написать очевидное неравенство : [a]<=a
mathgenius
На олимпиадах, как я выяснил, эта формула используется очень часто. Очень часто олимпиадники выучивают формулы вне школьного курса. Хотя я не исключаю, что данная задача может решаться и через метод математической индукции.
mathgenius
Но алгоритм весьма понятен и без самой формулы. В самом начале комментов все лаконично расписано
Answers & Comments
Сравним степени вхождения двойки в
и 
. В первом случае, очевидно, 
. Во втором: ![v_{2}(n!)=\sum\limits_{i=1}^{\infty}[\frac{n}{2^{i}}]< \sum\limits_{i=1}^{\infty}\frac{n}{2^{i}}=n](https://tex.z-dn.net/?f=v_%7B2%7D%28n%21%29%3D%5Csum%5Climits_%7Bi%3D1%7D%5E%7B%5Cinfty%7D%5B%5Cfrac%7Bn%7D%7B2%5E%7Bi%7D%7D%5D%3C%20%20%5Csum%5Climits_%7Bi%3D1%7D%5E%7B%5Cinfty%7D%5Cfrac%7Bn%7D%7B2%5E%7Bi%7D%7D%3Dn "v_{2}(n!)=\sum\limits_{i=1}^{\infty}[\frac{n}{2^{i}}]< \sum\limits_{i=1}^{\infty}\frac{n}{2^{i}}=n")
. Поэтому 