Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

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)


[Все попытки] [Задача]


 
     
Югорский НИИ ИТ, Югорский ФМЛ