Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Найти количество делителей заданного числа n, заданного в диапазоне 1 <= n <= 10^18 - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Выделить в одномерном массиве знакочередующийся подмассив http://www.cyberforum.ru/cpp-beginners/thread693049.html
Выделить в одномерном массиве знакочередующийся подмассив....помогите плиз!
C++ Не могу разобраться с qmake С помощью QtDesigner создал 2 файла gotocelldialog.ui и main.cpp в папке gotocell , запускаю: qmake -project появляется gotocell.pro далее запускаю qmake и он создает мне две папки: Debug,... http://www.cyberforum.ru/cpp-beginners/thread693048.html
Вложенные циклы C++
Написать программу которая выводит рисунок * ** * * **** с помощью вложенных циклов
C++ Компилятор
Привет) Подскажите ,пожалуйста, по работе компилятора, он(компилятор) берет исходный код и работает с ним как с текстом, потом через ассемблерные вставки генерирует exe? Важен момент с исходным...
C++ Оперделить общую массу предметов (через цикл) http://www.cyberforum.ru/cpp-beginners/thread693022.html
Доброго времени суток. Прошу вас помочь с программой: Известна масса каждого из 12 предметов. Определить массу всего набора (необходимо выполнить через цикл, не через массив) Очень надеюьсь на вашу...
C++ Найти ошибки, которые не дают сделать асинхронный сервер Хотелось мне сделать обертку вокруг асио. Чтобы обьект класса в одно время был сервером, в другое клиентом. Чтобы все быстро бегало, захотелось асинхронностью занятся. В итоге, как сервер он не... подробнее

Показать сообщение отдельно
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
09.11.2012, 18:23
Для решения данной задачи мы воспользуемся одной из теорем комбинаторики.

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

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

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

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

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

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

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


Взял с ******** могу показать код, только он на паскале.
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru