Найти такое число A, что бы B делилось на C без остатка

@marinad777 · Регистрация: 22.10.2016

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

Необходимо найти такое число A, что бы B делилось на C без остатка.

Условие:
B = 1*2*3*...*(A-1)*A

Входной файл содержит число C, файл на выходе должен дать ответ.

Очень нужен исходник или часть исходника, где показывается, как именно проходит вычисление числа B. Желательно с комментариями. Заранее спасибо.

@Cyborg Drone · 14.12.2016, 14:39

Ответов про то, как вычислить факториал, на форуме хоть пруд пруди. Посмотрите похожие темы внизу этой страницы. Вот так оно "происходит":

Pascal
1
2
  В := 1;
  for i := 2 to A do B := B * i;

Комментарии излишни. Только знание того, как перемножить Nсколько чисел, Вам вряд ли поможет. Дело в том, что, используя стандартные типы данных, Вы можете получить точное значение только до 26!, и то только после того, как немножко потанцуете с бубном. Для "решения в лоб" при A > 26 придётся применять длинную арифметику. Возьмём, например, A=10000. Тогда A!=10000!≈2,85∙10³⁵⁶⁵⁹. Даже учитывая тот факт, что на конце этого числа 2480 нулей, как Вы собираетесь работать с числом из 33179 значащих цифр? А если взять максимальное число типа integer? Я даже боюсь представить, сколько это будет - 2147483647!, и что-то мне подсказывает, что для его представления может не хватить всех компьютеров Вашего города.

Ну и, задание как-то повнимательнее читать нужно... Где в задании сказано, что требуется найти какой-то там факториал? Правильный ответ: нигде. На самом деле, Вам нужно найти число A, факториал которого делится нацело на C. Ещё подозреваю, что не любое А, таких бесконечно много, а минимально возможное. И ещё есть неясности при C=1.

Ну и, чё ж делать?

Вырисовывается такое решение: раскладывать число на простые множители с учётом степеней этих множителей, то есть, представить C в виде

$https://www.cyberforum.ru/cgi-bin/latex.cgi? C=\prod_{i}p_i^{k_i} $

где p_i - простые числа (2, 3, 5, 7, 11, 13, 17, 19 ну и так далее), k_i - степени этих чисел, иными словами, k_i - это сколько раз можно поделить C на p_i нацело. Конкретные значения p_i и k_i выясняются при разложении. А далее искать такое A, при котором все эти множители с учётом их степеней делят A!. Для этой цели есть неплохое подспорье: известно, что какое-либо простое число p делит A! вот такое количество раз:

$https://www.cyberforum.ru/cgi-bin/latex.cgi? t = \lfloor \frac{A}{p}\rfloor+\lfloor \frac{A}{p^2}\rfloor+\lfloor \frac{A}{p^3}\rfloor+... $

Скобки означают округление до меньшего целого, в случае положительных чисел можно применять паскалевскую функцию trunc или оператор div. Получается, что нужно найти минимальное А, при котором t≥k для каждого p, причём, так как используются простые числа, коллизий при таком сокращении A! на C не возникнет, потому что фактически будет иметь место частичное разложение факториала на простые множители, степени при которых не менее, чем степени при аналогичных множителях в разложении C. Очевидно, что множители эти сокращаются.

Всем хороша формула, только вот узнать заранее количество слагаемых (n) не представляется возможным, и вычислить "A" при известном "k" в одно действие не получится. В принципе, не страшно, просто будем делить сомножители факториала, делящиеся на текущее pⁿ до тех пор, пока возможно. А далее, если k всё ещё не достигнуто, будем увеличивать A и делить его на p до тех пор, пока не поделим эти сомножители на p k раз (нацело, естественно). Естественно, не нужно делить каждый сомножитель факториала, достаточно делить те, которые кратны текущему p, а таковые различаются на это самое p.
Последний сомножитель и будет тем самым A для текущего p. Затем можно взять следующее p и k, проверить, подходит ли полученное A для этих p и k, и, если не подходит, опять продолжить увеличивать и делить сомножители факториала. Повторяем всё это, пока не станет C=1.

Насчёт разложения C. Простые множители C придётся искать от 2 до C div 2. Если бы нужно было определить простоту C, простые множители числа C имело бы смысл искать от 2 до $https://www.cyberforum.ru/cgi-bin/latex.cgi? \lfloor \sqrt{C} \rfloor $ . Если делителей не найдено, следовательно, C - простое число или 1, и тогда A=C. Если бы в условии было бы B=A!, не B=1∙2∙3∙...∙(A-1)∙A, то при C=1 было бы A=0, поскольку 0!=1.

Множители буду искать, начиная с меньших (то есть, с двойки) путём деления C на предполагаемые множители. Преимущество: очередное предполагаемое p в случае, если оно делит C, автоматически будет простым, поскольку на все предыдущие простые уже поделено. Можно сказать, эдакая комбинация нахождения множителей перебором и решета Эратосфена.

Судя по стилю вопроса, скорее всего, задание Ваше с "олимпийского" сайта. Пишем программу для робота.

Pascal
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
var a, at, c, k, p, pn: integer;
begin
  //assign(input, 'input.txt');
  //reset(input);
  readln(c);
  //close(input);
  a := 1;
  for p := 2 to c div 2 do //перебираем простые делители числа, за исключением, может быть, c
    begin
      if c = 1 then break; //если все простые делители найдены, то досрочно выходим из цикла
      k := 0; //количество найденных делителей, равных p, пока 0
      while c mod p = 0 do //делим, если возможно, c на p и подсчитываем количество p
        begin
          inc(k);
          c := c div p
        end;
      pn := p; //степень p, пока p^1
      while (a >= pn) and (k > 0) do //определяем, делит ли p^k текущее b=a! по "всем хорошей формуле"
        begin
          k := k - a div pn; //вычитаем из k количество делителей p
          pn := pn * p //следующая степень p
        end;
      while k > 0 do //если p^k не делит a! (делители остались, k > 0), то увеличиваем a до тех пор, пока p^k не разделит a!
        begin
          a := a + p - a mod p; //следуещее a, кратное p
          at := a; //чтобы не потерять a, копируем его в буферную переменную
          while at mod p = 0 do //делим a на p, пока возможно
            begin
              at := at div p; //делим a на p
              dec(k) //уменьшаем оставшееся количество делителей
            end
        end
    end;
  //assign(output, 'output.txt');
  //rewrite(output);
  if a > 1 //если c не простое или не 1 (делители найдены),
    then writeln(a) //то печатаем a
    else writeln(c); //иначе, если c - простое или 1, печатаем c
  //close(output)
end.

Если всё-таки B=A!, то замените строки 36-38 на

Pascal
36
37
38
39
40
  if a > 1 //если делители найдены,
    then writeln(a) //то печатаем a
    else if c > 1 //иначе, если с не равно 1
      then writeln(c) //то a=c
      else writeln(0); //иначе a=0

Вот, как-то так, без никакого факториала.

Если для сайта нужен будет именно файловый ввод-вывод, раскомментируйте строки с переназначением стандартного ввода-вывода на файлы.

Если требуется C > 2147483647, то, во-первых, если возможно, Вам нужно будет сменить Ваш диалект паскаля на что-нибудь более серьёзное, чем Pascal ABC, например, на Free Pascal, переменные определить как int64, тогда C может быть до 9223372036854775807. Ещё придётся заменить цикл for на, например, while. Аналогичным образом можно увеличить C до 18446744073709551615, объявив все переменные, кроме k, как uint64, а k - как int64. Увеличить C до запредельных высот можно, применив Pascal ABC.NET, если возможно, и для переменных применив тип biginteger, но в этом случае требуется существенная переработка программы. Ну, или применив длинную арифметику, но тогда робот подавится. Вообще говоря, то, что я написал - для робота в самый раз.

Новые блоги и статьи Все статьи Все блоги /
Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита, которое может. . .	Команды "Заполнить" и "Очистить" на форме документа Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". На примере нетипового документа разработанного в конфигурации КА2. В качестве источника данных указан регистр накопления, в который записываются данные о. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .
Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .	SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip

@marinad777 1 / 1 / 0 Регистрация: 22.10.2016 Сообщений: 12

	Найти такое число A, что бы B делилось на C без остатка 07.12.2016, 12:36. Показов 1808. Ответов 1 Метки нет (Все метки) Необходимо найти такое число A, что бы B делилось на C без остатка. Условие: B = 123...(A-1)*A Входной файл содержит число C, файл на выходе должен дать ответ. Очень нужен исходник или часть исходника, где показывается, как именно проходит вычисление числа B. Желательно с комментариями. Заранее спасибо. 0

Найти такое число A, что бы B делилось на C без остатка

Решение