Найти наибольшее натуральное число x меньшее k такое что x!+(x−1)! кратно числу k

@11lamer11 · Регистрация: 10.12.2023

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

Ограничение по времени на тест 1s.
Ограничение по памяти на тест 256 MB.
Вам дано натуральное число k. Найдите наибольшее натуральное число x , где 1≤x<k , такое, что x!+(x−1)!† кратно числу k, или определите, что такого x не существует.
y! обозначает факториал числа y: 0!=1 , а для y≥1 факториал задаётся рекуррентно: y!=y⋅(y−1)!. Например, 5!=5⋅4⋅3⋅2⋅1⋅0!=120
.

Входные данные
Первая строка содержит одно целое число t (1≤t≤104) — количество наборов входных данных. Далее следует описание наборов.
Единственная строка каждого набора входных данных содержит одно целое число k (2≤k≤109).

Выходные данные
Для каждого набора входных данных выведите одно целое число — наибольшее возможное натуральное число x , удовлетворяющее условиям выше. Если такого x не существует, выведите −1
.
Вот мое решение:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
using namespace std;
 
// Функция для нахождения наибольшего x для данного k
int find_largest_x(int k) {
    // Проверяем x от k-1 до 1
    for (int x = k - 1; x >= 1; --x) {
        long long factorial_x = 1, factorial_x_minus_1 = 1;
 
        // Вычисляем x! % k
        for (int i = 1; i <= x; ++i) {
            factorial_x = (factorial_x * i) % k;
        }
        
        // Вычисляем (x-1)! % k
        for (int i = 1; i < x; ++i) {
            factorial_x_minus_1 = (factorial_x_minus_1 * i) % k;
        }
        
        // Проверяем условие
        if ((factorial_x + factorial_x_minus_1) % k == 0) {
            return x; // Возвращаем x, если условие выполнено
        }
    }
    return -1; // Если такого x нет
}
 
int main() {
    int t; // Количество тестов
    cin >> t;
 
    while (t--) {
        int k;
        cin >> k;
 
        // Вывод результата для текущего k
        cout << find_largest_x(k) << endl;
    }
 
    return 0;
}

Превышено ограничение времени на тесте 2.

@Royal_X · 27.11.2024, 22:44

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

Про 1000 я и не говорю

Это тоже быстро вычисляется. По крайней мере, моя библиотека для работы с большими числами справляется за миллисекунды. А тут даже по условию всего до 109.

Найти наибольшее натуральное число x меньшее k такое что x!+(x−1)! кратно числу k

Но если говорить о факториале 10^9, то только для хранения результата в виде строки нужно более 8 ГБ. Есесена считать не получится.

Новые блоги и статьи Все статьи Все блоги /
Установка ChatGPT (Codex) на Windows без использования Microsoft Store Fabien159 28.10.2026 Здравствуйте всем читающим! Опишу процесс установки ChatGPT (Codex) на Windows, если по каким-то причинам у вас не получается устанавить его через Microsoft Store. И так: 1. Скачиваем с. . .	Программное добавление префикса в нумерацию документов Maks 27.10.2026 Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге). Задача: Программно добавить префикс в нумерацию документов. Решение: В модуле объекта. . .	После закрытия оутлука продолжает висеть процесс в диспетчере задач Maks 27.10.2026 С недавнего времени в продакшене возникла проблема: при закрытии оутлука в диспетчере задач продолжал висеть процесс outlook. exe. Проблема возникла после установки MS Office 2021 LTSC на машинах, под. . .	Baragoz - DPS/HPS бот для WoW 3.3.5a, многоязычный AmbA 26.10.2026 Хотите ещё ботов? У меня есть один! А я пока отдохну от него. https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=12062&stc=1&d=1793007952 Инструкция внутри. https:/ / youtu. be/ VpfFZSUDGnQ. . .
Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .