Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Количество делителей

(Время: 1 сек. Память: 16 Мб Сложность: 50%)

Для решения данной задачи мы воспользуемся одной из теорем комбинаторики.

Теорема. Если существует K классов, содержащих соответственно n1 , n2 , . . . nK элементов, то число различных способов выбора элементов равно (n1 + 1)(n2 + 1)...(nK + 1)

Для определенности рассмотрим на примере. В коробке лежат 10 шаров синего, 8 красного и 5 желтого цветов. Сколькими способами можно достать данные шары из коробки? Разумеется, что все шары доставать необязательно, например, можно достать 2 синих, 4 желтых и 3 красных шара, или 1 синий и 5 желтых. А ведь можно и вообще их не доставать, этот случай тоже является случаем выбора шаров, в результате которого получается пустое множество выбранных элементов.

Для ответа на этот вопрос следует воспользоваться вышеприведенной теоремой. Мы имеем три класса:

  1. Шары синего
  2. Желтого
  3. Красного цветов

Число элементов первого класса равно 10, второго - 8, третьего, соответственно, 5. Тогда общее количество возможных вариантов выбора будет равно S = (10 + 1)(8 + 1)(5 + 1) = 594. То есть число различных способов выбора шаров из коробки равно 594.

Эту задачу можно было бы решать и методом полного перебора, что значительно увеличит время выполнения программы.

Теперь проведем аналогию между нашей задачей и задачей про шары. Основная теорема арифметики гласит, что любое натуральное число можно представить в виде произведения простых чисел, входящих в разложение данного числа в различных степенях. Классом в нашем случае является простое число. Количеством элементов - степень, в которой это число входит в разложение.

Тогда для решения задачи необходимо разложить число x на простые множители, посчитать сколько раз встречается каждое простое число в разложении и перемножить соотвествующие результаты в соответствии с вышеприведенной формулой.

Разбор: Калмыков Вадим (ProCrypt)


[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru