Задача на арифметику остатков

@maksvolf96 · Регистрация: 18.05.2014

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

Здравствуйте, есть задача :

Срочно нужно посчитать факториал чила. Срочно! Сейчас же!!! Ну ладно хотя бы по модулю 10^9 + 7. Но срочно!

Входные данные
В единственной строке дано число N (0 ≤ N ≤ 10^8) — факториал которого нужно вычислить.

Выходные данные
Выведите результат вычисления факториала по модулю.

Код

C++
1
2
3
4
5
 while(i <= N)
    {
        res = ( (res % c)*(i % c) ) % c;
        i++;
    }

Не проходит по времени, что можете посоветовать, спасибо

@Renji · 01.10.2015, 00:52

По табличке. Хрен его знает пройдет ли по лимитам времени, но точно будет быстрее чем у вас.

C++
1
2
3
4
5
6
7
8
9
const int div=10000;
int table[]={готовая таблица факториалов от N*div. Факториал нуля считается за единицу};
int fact(int n)
{
    int64_t res=table[n/div];
    for(int i=(n/div)*div+1;i<=n;++i)
        res=(res*i)%1000000007;
    return res;
}

@Barrent · 01.10.2015, 01:39

Формула Стрилинга?

Во многих случаях для приближённого значения факториала достаточно рассматривать только главный член формулы Стирлинга:

@maksvolf96 · 01.10.2015, 01:48 **[ТС]**

Renji, поясните, пожалуйста как она работает и как я смогу запихнуть в тип int факториалы чисел от 0 до 9999, например n = 20100, тогда res = 2, i = 20001, а перебор происходит от 20001 до 20100, то есть res будет
(2 * 20001) % и т.д., но это уже совсем неясно, почему мы 2* 20001? спасибо

@Renji · 01.10.2015, 01:59

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

Renji, поясните, пожалуйста как она работает и как я смогу запихнуть в тип int факториалы чисел от 0 до 9999

Поправка - "таблица факториалов от N*div % 1000000007".

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

например n = 20100, тогда res = 2, i = 20001

Тогда res=(факториал 2*10000)%1000000007. В табличке факториалы идут с шагом 10000.

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

@maksvolf96 3 / 3 / 2 Регистрация: 18.05.2014 Сообщений: 203
	01.10.2015, 01:48 [ТС]
	Renji, поясните, пожалуйста как она работает и как я смогу запихнуть в тип int факториалы чисел от 0 до 9999, например n = 20100, тогда res = 2, i = 20001, а перебор происходит от 20001 до 20100, то есть res будет (2 * 20001) % и т.д., но это уже совсем неясно, почему мы 2* 20001? спасибо 0