Задача
Президент Першого національного Банку майор Томаса Б. Кiнгмена кожну ніч перекладає вміст сейфів, у яких клієнти банку зберігають свої коштовності. Грабіжникам це також відомо, і тому вони орендували один із сейфів у цьому банку й чекають, поки президент перекладе в їхній сейф щось цінне. Таким чином до їхніх рук потрапила скринька з коштовностями самого майора! Тепер у грабіжників є всього лиш кілька годин для того, щоб відкрити кодовий замок з трьох цифр, забрати цінності й повернути скриньку назад, щоб ніхто навіть не дізнався, що пограбування взагалі відбулося.
Знаючи пристасть майора до великих чисел, грабіжники переконані, що кодом є три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$. Наприклад:
- при $N$ = $7$ кодом буде $504$, бо $7!$ = $5040$;
- при $N$ = $17$ кодом буде $096$, бо $17!$ = $355687428096000$.
За даним натуральним числом $N$ знайти три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$.
Вхідні дані
Вхідний файл містить єдине ціле число $N$. $(7 \leqslant N \leqslant 1000000000)$.
Вихідні дані
Вихідний файл має містити рівно три цифри — шуканий код.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 7 | 504 |
| 2 | 17 | 096 |
| 3 | 50 | 512 |
| 4 | 1000000000 | 144 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> #define COEF 10000000 #define TEN 10 using namespace std; unsigned int arr[] = { 1, 94194688,80754176,28792576,93638144,44194688,16269824,94550272,61946112,68933632, 68754176,19323648,22612992,36351232,57997312,66792576,2167808,95748096,88043776, 37690112,65638144,99247872,80831232,42968832,38960896,2194688,36401664,29433088, 21091328,35679232,40269824,3200512,39416576,62174976,23727104,49750272,52626176, 72337664,68916224,93513984,25146112,14722816,60257024,2170112,13989632,28933632, 91983872,29619968,23259904,52859904,2354176,61171456,14485248,81225984,93129472, 98123648,42294528,83940096,91339008,90945024,77812992,83786752,30308352,33122816, 709376,45551232,13495552,4053504,28486912,65094912,93197312,79194112,80894208, 48729344,89670656,26832576,59147776,51826688,14217984,72698112,10487808,29000448, 21455616,72560128,94383616,23588096,83462144,14917632,85698816,11810304,3083776, 84299264,11034368,6525952,27101696,68170112,92235008,45980416,15386112,44244224, 3398144 }; int main() { int N; unsigned long long factorial = 1; cin >> N; int idx = N/COEF; factorial = arr[idx]; int start = !N%COEF ? idx*COEF : idx*COEF + 1; if (N % COEF != 0) { for(int i = start; i <= N; i++) { factorial *= i; while(factorial % TEN == 0) factorial /= TEN; factorial %= COEF; } } factorial %= TEN*TEN*TEN; cout << factorial/(TEN*TEN) << (factorial/TEN)%TEN << factorial%TEN; return 0; } |
Решение
Поскольку процесс расчёта факториала больших чисел занимает много времени, его можно ускорить использованием массива факториалов некоторых чисел. Полное значение факториала не нужно, поэтому массив содержит последние $8$ ненулевых цифр значений факториалов чисел, кратных $10000000$, которые можно получить с помощью следующего кода:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> #define TEN 10 using namespace std; int main() { int N = 1000000000, count = 1; unsigned long long factorial = 1; for(int i = 1; i <= N; i++) { factorial *= i; while(factorial%TEN == 0) factorial /= TEN; factorial %= 100000000; if (i % 10000000 == 0) {cout << factorial << ","; count++;} if (count == TEN) {cout << endl; count = 1;} } return 0; } |
Если на входе — число $N$, меньшее $10000000$, его факториал рассчитывается обычным циклом, попутно отбрасывая ненужные цифры высших разрядов. В конце выводятся искомые последние три цифры факториала числа $N$. Если на входе — число $N$, большее $10000000$, выбирается соответствующее значение из массива по индексу $N/10000000$, и далее с помощью цикла считается произведение оставшихся чисел из $N!$. С уменьшением кратности чисел, факториалы которых содержатся в массиве, увеличивается скорость выполнения программы.
Ссылки
- Код на ideone
- Задача на e-olymp
- Засчитанное решение на e-olymp
— Хорошее решение. Не был уверен, что Вы справитесь. Но если осилили, буду давать задачи сложнее. Молодец.
— Как вы получили числа из массива? Была какая-то вспомогательная программа?
— Почему у Вас на аватарке обезьянка?
— После «Наприклад:» должен идти маркированный список (UL). Для разметки элементов списка есть кнопки в редакторе, но проще написать самому пару тегов.
— Уберите пустые строки.
— Добавьте тесты для краев допустимого диапазона входных значений.
Была вспомогательная программа. Замечания исправила.
— Да, хорошо, что использовали вспомогательную программу. Это частая практика — предварительно что-то вычислить. Только нужно это написать и привести код.
— Пожалуйста, уберите кириллицу из адреса работы (постоянная ссылка).
Добавила этот код в описание решения. Ссылку изменила.