Какое наименьшее количество множителей требуется вычеркнуть?

[gris]

fractalon, спасибо. Правда, я имел в виду есть ли такая команда в языках, ну типа $delmod(a;b;m)$, а то всё кодировать пальчики отбить можно

[Yadryara]

fractalon в сообщении #1105035 писал(а):

Отсюда и $625$ и $119$.

Очепятка? Ведь не $119$, а $199$.

Не разобравшись, как использовать обратный элемент и алгоритм Евклида, решал вот таким способом.

Наше диофантово уравнение:

$$x = \frac{74 + 625a}{126 + 625b}$$

Здесь $a$ и $b$ целые неотрицательные, $1 \le x \le 2016$.

Положив $a=0$ и $b=0$, начал наращивать $a$ на единицу.

$74 + 625\cdot 0 \equiv 74\ (\mod 126)$
$74 + 625\cdot 1 \equiv 69\ (\mod 126)$
$74 + 625\cdot 2 \equiv 64\ (\mod 126)$

Остаток циклически уменьшается на $5$, значит $a = \frac{74 + 126c}5$. Видно, что $a$ будет принимать целые значения при $c = 5k + 1$, где $k = 0,1,2...$

$a = \frac{74 + 126(5k+1)}5 = 126k + 40$

Подставляем:

$$x = \frac{74 + 625(126k + 40)}{126}= 625k + 199$$

Действуя аналогичным способом, можно убедиться, что решений для $b>0$ нет.

[fractalon]

Не разобравшись, как использовать обратный алгоритм Евклида, вы его использовали. По крайней мере, его идею. Идея ведь в том, что берётся остаток от деления модуля на делимое (делимое в нашем случае $126$). Здесь остаток будет равен $121$, но $121 \equiv -5 \pmod{126}$, поэтому можно посчитать и за $-5$. Дальше делается такой перевёртыш как вы сделали и всё продолжается итеративно точно так же. Просто здесь удачный случай и алгоритм Евклида работает в два хода (а вообще ходов у него максимум - порядка логарифма; худший пример - применение алгоритма к двум последовательным числам Фибоначчи). Двуходовость алгоритма как бы ещё раз намекает, что задачу нужно было решать так и бумажки достаточно.

А про $119$ и $199$ - да, опечатка.

[gris]

Понял, что разделить можно и на бумажке. Но как без компьютера получить, что $2016!$ (без кратных пяти, спасибо за поправку) кончается на $1184$

[Yadryara]

fractalon в сообщении #1105899 писал(а):

Не разобравшись, как использовать обратный алгоритм Евклида, вы его использовали. По крайней мере, его идею.

Так и думал Спасибо.

fractalon в сообщении #1105899 писал(а):

Идея ведь в том, что берётся остаток от деления модуля на делимое (делимое в нашем случае $126$).

То есть $b$ всегда надо приравнивать к нулю? Похоже, что так. Ведь при бо́льших значениях $b$ никаких новых решений найти не удалось:

$b = 1; a = 990; x = 824$

$b = 2; a = 1390; x = 1449$

gris в сообщении #1105920 писал(а):

Но как без компьютера получить, что $2016!$ кончается на $1184$

Поправочка. На $1184$ закачивается не $2016!$ , а $\frac{2016!}{5^{403}\cdot403!}$

[Yadryara]

Кстати, в духе ТС неплохо бы ввести терминологию, чтобы не путаться. Факториал, из которого вычеркнуты все кратные $5$, назовём беспятым.

Гипотеза. Беспятый факториал(БПФ) числа, оканчивающегося на $4$, всегда оканчивается на $24$. А БПФ числа, оканчивающегося на $9$, всегда оканчивается на $76$.

Таким образом, БПФ $2014$ и БПФ $2019$ оканчиваются на $24$ и $76$ соответственно.

Насчёт БПФ 2016. Нетрудно установить, что он оканчивается на $4$

[Yadryara]

Отвечая на вопрос gris'а.

Оказывается, концовки БПФ довольно предсказуемы. Чтобы найти 4-значную концовку для чисел БПФ $n$, оканчивающихся на $16$ или $66$, можно воспользоваться формулой:

$$100((\frac{26(n - 16)}{25} + 31)\mod 100) + 84$$

Что для БПФ $2016$ как раз даёт $1184$. А, к примеру, для БПФ $2906$ нужна формула:

$$100((\frac{26(n - 6)}{25} + 1)\mod 100) + 44$$

Дающая концовку $1744$.