Цитата(Akina @ 9.11.2004, 07:25)

chaos Это я к тому что для чисел менее 25 достаточно просчитывать последнюю ненулевую цифирь, для чисел 26-50 - уже 2, до 75 - три, до 100 - 4, до 125 - 5, до 150 - уже 7... в общем по n-1 дополнительной хвостовой цифири для каждого множителя, делящегося на 25 (где n - кол-во пятерок средим его простых множителей)...

По-моему, надо запоминать только 2 последние ненулевые цифры, остальные просто смысла нет помнить. Ведь в формировании последней цифры участвуют всего две...

Цитата

По-моему, надо запоминать только 2 последние ненулевые цифры, остальные просто смысла нет помнить. Ведь в формировании последней цифры участвуют всего две...

действительно так, но: а вдруг эта цифра станет нулевой?
тогда последней цифрой становится другая, в формировании которой принимали участие другие цифры

maxim1000
Да, ты прав.
И мое решение выдает ошибку при факториале 25... (Сегодня проверил)

chaos:

Цитата

Определить последнюю цифру не равную 0 при вычислении факториала N!, причем N задается в пределах от 1 до 10000

Эту задачу школьники решают!
Факториал числа с некоторого номера заканчивается нулями. Нули беруться только от перемножения двоек на пятерки. Кого больше? Ясно пятерок. Поэтому, подсчитаем кол-во пятерок, входящих в n!(n div 5 + n div 25 + ....).
Теперь начнем считать нашу последнюю цифру, выкидывая все пятерки и такое же кол-во двоек:

Код

var  n, k, s, t, i, j : integer; begin  read(n);  k := n div 5;  s := 0;  while k > 0 do    begin      s := s + k;      k := k div 5    end;  t := 1;  for i := 2 to n do  begin    j := i;    while j mod 5 = 0 do      j := j div 5;    while (s > 0) and (j mod 2 = 0) do      begin        j := j div 2; s := s-1      end;    t := t*(j mod 10) mod 10  end;  write(t); end.

GePo

Цитата

N задается в пределах от 1 до 10000

Догадываешься куда пошел твой алгоритм? туда же куда и наши - в математику длинных чисел. В том виде в каком он приведен...

Однако кое-что интересное тут есть - попробую дома накидать алгоритм, поздно уже...

GePo
Что-то у меня алгоритм не работает...

Akina

Цитата

Догадываешься куда пошел твой алгоритм? туда же куда и наши - в математику длинных чисел. В том виде в каком он приведен...

ЧЕГО????? там все вычисления по модулю десять идут! до хоть n до миллиона!

Alex101
на каких примерах не работает? вообще этот алгоритм точно правильный, не только я это придумывал, но и написано это где-то. Я его сейчас просто вспомнил

GePo
24
Зацикливается...

Alex101
Не понял... у меня все нормально... Где он вообще может зацклиться?

Это сообщение отредактировал(а) GePo - 12.11.2004, 19:18

to GePo

Цитата

И мое решение выдает ошибку при факториале 25... (Сегодня проверил)

Можно спросить на чем ты проверял ?

Это сообщение отредактировал(а) Freeman - 12.11.2004, 22:40

Freeman
цитата не моя

можете проверить ещё одно число
2004! -> 2

Цитата(Kefir @ 12.11.2004, 23:39)

можете проверить ещё одно число 2004! -> 2

совпадает... а какой источник?
2005! -> 6 (это моя программа дает)

maxim1000 источник - линуксовский калькулятор (не помню как называется...)
можешь ещё проверить:
100 000! -> 6
а сколько у тя прога считает для 2004?

Цитата

а сколько у тя прога считает для 2004?

незаметно

Цитата

можешь ещё проверить: 100 000! -> 6

я рассчитывал на числа до 10 000, для больших не работает, т.к. хранятся последние цифр (если отбросить нули), а значит, умножение на число порядка 10^5 даст число порядка 10^10, что в 32 разряда не помещается
так что та программка, которую я привел не подойдет
НО:
если там изменить

Код

x%=100000;

на

Код

x%=10000;

то все заработает
получается 6
считает практически так же незаметно...
кстати, заметил у себя один багик (или бажик ):
надо еще добавить

Код

while(qqq%10==0)  qqq/=10;

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

Код

int func(unsigned int n) {  unsigned int x,c;  x=1;  for(c=1;c<=n;c++)  {    int qqq=c;    if(c==50000)      c=c;    while((x%2==0)&&(qqq%5==0))    {      x/=2;      qqq/=5;    }    while((x%5==0)&&(qqq%2==0))    {      x/=5;      qqq/=2;    }    while(qqq%10==0)      qqq/=10;    x*=qqq;    x%=10000;    //cout<<"   "<<x<<"\n";  }  return x%10; }