Делители

@Evgexa92 · Регистрация: 08.10.2019

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

Задано число n. Требуется найти число от 1 до n, включительно, которое имеет
максимальное число положительных целых делителей.
Например, если n = 20, то искомое число — 12, у него 6 делителей: 1, 2, 3, 4, 6, 12.
-------------------------------------------------------------
Формат входных данных
На вход подается одно число n (1 ≤ n ≤ 105)
-------------------------------------------------------------
Формат выходных данных
Выведите на первой строке число от 1 до n, включительно, которое имеет мак-
симальное число делителей. На второй строке выведите число его делителей.
Если есть несколько чисел от 1 до n с максимальным числом делителей, выведите
любое из них.
------------------------------------------------------------
Примеры
standard input
20
standard output
12
6

@Puporev · 08.10.2019, 17:29

Наверное 1<n<=10⁵?

@Evgexa92 · 08.10.2019, 17:35 **[ТС]**

да,сейчас исправлю

Добавлено через 4 минуты
Можешь пожалуйста помочь,завтра олимпиада ,а я решить не могу,очень срочно нужно

@Joy · 08.10.2019, 17:52

не мое

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
//отсюда https://**********************/questions/352481/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA-%D1%87%D0%B8%D1%81%D0%BB%D0%B0-%D0%B8%D0%BC%D0%B5%D1%8E%D1%89%D0%B5%D0%B3%D0%BE-%D0%BD%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B5-%D1%87%D0%B8%D1%81%D0%BB%D0%BE-%D0%B4%D0%B5%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D0%B5%D0%B9
var  p:array of integer:=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47);
     answer, cntForAnswer,N:int64;
 
//index - индекс простого числа p[index], на который сейчас будем пробовать умножать
//lastA - значение предыдущего значения ai, что бы составить не возрастающую (a[i+1]<=a[i])
//value - текущее значние (p1^a1)*(p2^a2)*...*(pi^ai)
//cntForValue - количество делителей числа value
procedure findMax(index, lastA, value, cntForValue:int64);
begin
    if (cntForValue > cntForAnswer) or ((cntForValue = cntForAnswer) and (value < answer)) then begin
        answer := value;
        cntForAnswer := cntForValue;
    end;
    if(index = 15) then exit;
    for var a:=1 to lastA do begin
        var temp := value * p[index];
        // проверка на переполнение
        if(temp/p[index] <> value) then exit;
        // если получили число больше N
        if(temp > N) then break;
        value := temp;
        findMax(index+1, a, value, cntForValue*(a+1));
    end;
end;
 
begin
  readln(n);
  findMax(0, 64, 1, 1);
  writeln(answer);
  writeln(cntForAnswer);
end.

алгоритм
Существует решение и для чисел до 10^18.

Обозначения

Пусть искомое число X представимо в виде: (p1^a1)(p2^a2)...*(pk^ak), где pi - простое число, причем pi < pj при i < j, т.е. простые числа взяты по возрастанию.

Количество делителей cnt(X) = (a1+1)(a2+1)...*(ak+1) - это справедливо, даже если какие то степени ai = 0

Наблюдения:

Количество делителей зависят от показателей степени простого числа, которое в него входит, но не от самого простого числа.
Пусть последней ненулевой степенью будет ak, надо заметить, что нам не выгодно что бы на отрезке i=1...k-1 была ai=0, это значило бы, что мы можем сдвинуть массив степеней влево и при этом: число уменьшится, количество делителей останется таким же.
Так же нам выгодно, что бы массив ai создавал невозрастающую последовательность, иначе мы можем отсортировать данным массив по не возрастанию и мы получим меньшее число с таким же количеством делителей.
Количество простых чисел которое мы хотим рассматривается k<=15 для N<=10^18. Из соображений, что если перемножить первые 16 простых чисел получим число превышающее 10^18.
Из этих соображений строим алгоритм:

Необходимо перебрать все возможные последовательности ai не более из 15 элементов, удовлетворяющие следующим условиям:

последовательность ai - невозрастающая
(p1^a1)(p2^a2)...*(pk^ak) <= N
Среди таких последовательностей выбрать ту, где (a1+1)(a2+1)...*(ak+1) - максимально.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .

@Evgexa92 0 / 0 / 0 Регистрация: 08.10.2019 Сообщений: 13

	Делители 08.10.2019, 17:10. Показов 3230. Ответов 3 Метки нет (Все метки) Задано число n. Требуется найти число от 1 до n, включительно, которое имеет максимальное число положительных целых делителей. Например, если n = 20, то искомое число — 12, у него 6 делителей: 1, 2, 3, 4, 6, 12. ------------------------------------------------------------- Формат входных данных На вход подается одно число n (1 ≤ n ≤ 105) ------------------------------------------------------------- Формат выходных данных Выведите на первой строке число от 1 до n, включительно, которое имеет мак- симальное число делителей. На второй строке выведите число его делителей. Если есть несколько чисел от 1 до n с максимальным числом делителей, выведите любое из них. ------------------------------------------------------------ Примеры standard input 20 standard output 12 6 0

@Puporev Почетный модератор 64315 / 47611 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	08.10.2019, 17:29
	Наверное 1<n<=10⁵? 1

@Evgexa92 0 / 0 / 0 Регистрация: 08.10.2019 Сообщений: 13
	08.10.2019, 17:35 [ТС]
	да,сейчас исправлю Добавлено через 4 минуты Можешь пожалуйста помочь,завтра олимпиада ,а я решить не могу,очень срочно нужно 0

Делители

Решение