Как найти последную ненулевую цифру K!?

Question

[lil_web]

Задачка по программированию. Помогите решить.

Маша составляет последовательность, где на K месте стоит последняя ненулевая цифра K!. Помогите ей заполнить пропуски.

Входные данные:
Первая и единственная строка содержит число K (0 ≤ K ≤ 10⁵)

Выходные данные:
Последная ненулевая цифра K!

Пример: ввели 5, вывелось 2.

Comments

[Модератор]

lil_web дорогой пользователь, настоятельно рекомендуем еще раз обратить самое пристальное внимание на п. 3.1 регламента работы сервиса (и, в особенности, на его последний абзац). В противном случае, ваши вопросы будут удаляться по причине тег-спама, а систематические нарушения приведут к блокировке учетной записи.

[lil_web]

Модератор, оки. Но это не просто пыха, такая задачка может быть на любом ЯП. Поэтому считаю хотя бы тег «Алгоритмы» верным.

[Модератор]

lil_web, да не вопрос. Но зачем тогда указывать конкретный язык?

[lil_web]

Модератор, чтобы получить ответ на нём, потому что я его знаю лучше, чем другие ЯП. Можно и на другом языке, главное — ответить)

[dollar]

Пример: ввели 5, вывелось 2.

В числе 5 последней ненулевой цифрой будет 5. Откуда 2?

[jcmvbkbc]

dollar, факториал, 5! = 120 => 2

[dollar]

jcmvbkbc, господи, я думал это эмоции в вопросе.

Тогда всё просто. Сначала вычисляем факториал, переводим резульатат в строку, и с конца ищем нужную цифру. Либо еще можно брать остаток от деления на 10, пока не получим цифру или пока само число не кончится.

[dollar]

А стоп. Там же заоблачные значения K

[jcmvbkbc]

dollar, я думаю, что смысл задачи в том, чтобы не использовать длинную арифметику. С длинной арифметикой она действительно элементарно решается.

[dollar]

Это сложно. Задача явно искусственная, придуманная математиком. Так что здесь не столько программирование, сколько математика.

Вряд ли всё сводится к какой-то формуле вида f(K), иначе бы программирование с алгоритмами было бы вовсе не при чем. Значит, подразумевается какой-то перебор.

Очевидно, что узкое место в том, что большие числа не помещаются в размерность регистров процессора. Значит, должен быть способ как-то сокращать числа. И при этом всё же потребуется перебрать их все (вплоть до 10⁵).

Первое, что приходит в голову - убирать 10, а также 2*5. То есть если очередной множитель оканчивается на нули, то просто убирать их. Дальше ищем пары чисел: одно кончается на 5, другое четное. Делим соответственно.
Вместо 1,2,3,4,5 должно остаться 1,1,3,4,1. Ну или 1,2,3,2,1 (смотря как перебирать, хе).

Далее таким же образом нужно как-то сокращать остальные числа. Как именно - с ходу не скажу, надо думать. Как я и сказал, это больше математическая задачка. Т.е. это задача, а не вопрос.

[Lynn «Кофеман»]

Это просто, последняя ненулевая цифра к! Зависит от последней ненулевой цифры (к-1)! и к

[#]

копайте в сторону признаков делимости. для примера - только 2 и 5 (а так же любые их степени) дают 10, при этом мы явно говорим о десятичной системе счисления

[#]

была мысль, проверил, в лоб не работает. ответ удалил.. если соображу как правильно - напишу новый ))

[Lynn «Кофеман»]

Неправильный алгоритм:

ц = 1
Цикл ч от 2 до к
  в = ц * ч
  Пока в делится на 10
    в = в / 10
  Конец цикла
  ц = последняя цифра в
Конец цикла
Вернуть ц

Вроде надо запоминать не одну последнюю цифру, а несколько

[Wataru]

Алексей Тен, Зависит от всех последних ненулевых цифр в (k-1)! Потому что ...15*2 =...30, а ...25*2=50

Answer 1

[Антон Федорян]

ideone

<?php

function normalize($num)
{
	while ($num % 10 == 0)
	{
		$num = intdiv($num, 10);
	}
	
	return ($num % 100);
}

$k = 50; //  k! = 30414093201713378043612608166064768844377641568960512000000000000
$result = 1;

for ($i = 2; $i <= $k; $i++)
{
	$result = normalize($result * $i);
}

echo $result % 10; //  2

Answer 2

[Wataru]

Можно быстро, за log (k) подсчитать, сколько там нулей в k!

Для этого какая там степерь 2 и 5 и возьмите минимум.
Простое p войдет в k! в степени floor(k/p) + floor(k/p^2) + floor(l/p^3)...
Можно легко это реализовать рекурсивно PowerInFactorial(n, p) = n >= p ? n/p + PowerInFactorial(n/p) : 0;

Теперь вы знаете, сколько нулей в факториале. Если их все убрать, то задача становится совсем простой - найти последнюю цифру. Это можно сделать просто ведя все вычисления по модулю 10.

Т.е. перемножаете все числа от 2 до k, предворительно сокращая двойки и пятерки, сколько надо.

twos = fives = min(PowerInFactorial(k, 2), PowerInFactorial(k, 5));
ans = 1;
for ( i = 2; i <= k; i++) {
  j = i;
  while (j % 2 == 0 && twos > 0) {
    j/=2;
    twos--;
  }
  // same for fives
  ...
  ...
  ans = (ans*j)%10;
}

В итоге решение за O(k), потому что вложенные циклы вполнятся суммарно столько раз, сколько нулей в k!, а их по формуле выше, меньше O(k).