Остаток от деления большого факториала на число+

@SiFlyer · Регистрация: 16.11.2019

Author24 — интернет-сервис помощи студентам

Добрый день! В ходе решения задачи передо мной встала задача что нужно разделить факториал на число, и получить его остаток. Сразу поясню, по условию, в лоб решать не получится, т.к. число факториала(т.е. не сам факториал, а число факториала) может достигать 100000 и возводить такое число в факториал будет слишком долго, нагрузно. Таким образом я решил спросить у вас) Есть ли какая-нибудь взаимосвязь между числом факториала, делителем и остатком? Надеюсь на вашу помощь

@_Ivana · 17.10.2020, 19:40

Есть, и тривиальная.

@SiFlyer · 18.10.2020, 15:34 **[ТС]**

можете пожалуйста написать ее?

Байт · 18.10.2020, 16:28

_Ivana, Давай!!! Мне все равно так коротенько, как ты, не написать! На и хлеб отбирать не хочу!

Ну а про гомоморфизм кольца целых чисел на кольцо вычетов ты знаешь не хуже меня.

Добавлено через 3 минуты
Слинял с форума _Ivana. За пивом пошел... Придется мне отдуваться

C++

1
2
3

int rest = 1;
for(i=2; i<=N; i++)
  rest = (rest*i)%d;

@SiFlyer · 20.10.2020, 09:07 **[ТС]**

К сожалению, я так и делал. Однако на тестах есть факториалы <5000 и если они не проходят проверки, то приходиться считать по вашему способу, но времени на это уходит куча

@TheCalligrapher · 20.10.2020, 09:12

Сообщение от SiFlyer

Однако на тестах есть факториалы <5000 и если они не проходят проверки, то приходиться считать по вашему способу, но времени на это уходит куча

Ничего не понятно. А каким же еще способом вы пытались считать?

Байт · 20.10.2020, 10:07

Небольшая модификация кода

C++

int testRest(int N, int m)
{
  if (m <= N) return 0;
  int rest = 1;
  for(i=2; i<=N; i++)
    rest = (rest*i)%m;
  return rest;
}

Можно еще поиграть в максимальный простой делитель m...

@_Ivana · 20.10.2020, 11:52

Сообщение от SiFlyer

но времени на это уходит куча

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

@SiFlyer 0 / 0 / 0 Регистрация: 16.11.2019 Сообщений: 14
		1
	Остаток от деления большого факториала на число+ 17.10.2020, 19:28. Показов 4710. Ответов 7 Метки нет (Все метки) Добрый день! В ходе решения задачи передо мной встала задача что нужно разделить факториал на число, и получить его остаток. Сразу поясню, по условию, в лоб решать не получится, т.к. число факториала(т.е. не сам факториал, а число факториала) может достигать 100000 и возводить такое число в факториал будет слишком долго, нагрузно. Таким образом я решил спросить у вас) Есть ли какая-нибудь взаимосвязь между числом факториала, делителем и остатком? Надеюсь на вашу помощь 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	17.10.2020, 19:40	2
	Есть, и тривиальная. 0

@SiFlyer 0 / 0 / 0 Регистрация: 16.11.2019 Сообщений: 14
	18.10.2020, 15:34 [ТС]	3
	можете пожалуйста написать ее? 0

@SiFlyer 0 / 0 / 0 Регистрация: 16.11.2019 Сообщений: 14
	20.10.2020, 09:07 [ТС]	5
	К сожалению, я так и делал. Однако на тестах есть факториалы <5000 и если они не проходят проверки, то приходиться считать по вашему способу, но времени на это уходит куча 0

@TheCalligrapher Вездепух 11691 / 6370 / 1723 Регистрация: 18.10.2014 Сообщений: 16,052
	20.10.2020, 09:12	6
	Сообщение от SiFlyer Однако на тестах есть факториалы <5000 и если они не проходят проверки, то приходиться считать по вашему способу, но времени на это уходит куча Ничего не понятно. А каким же еще способом вы пытались считать? 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	20.10.2020, 11:52	8
	Сообщение от SiFlyer но времени на это уходит куча А вы считайте не вручную а на компьютере, 5000 итераций для него это ерунда 0

Опции темы