Страницы

Поиск по вопросам

понедельник, 25 марта 2019 г.

Нахождение одного из чисел, если дан НОК двух чисел и второе число

Не могу понять, как эту задачу можно решить без "тупого" перебора чисел от НОК/данное число, до самого НОК. Число, которое нужно найти, должно быть минимальным подходящим к данным.
Можно выразить искомое число через НОД(неизвестный)*НОК/данное_число, но тогда не понятно, как обратно идти от НОД к числу. Также можно разложить НОК и дынное число на простые множители, по ним искать третье (опорная точка -- произведение чисел, которые есть в разложении НОК но нет в разложении данного нам числа), но тут как раз перебор с проверкой (правда, чуть поменьше). Второй вариант сложнее при очень больших числах.
Перебором нельзя т.к. числа будут огромные. Написать код не прошу, просто интересна сама суть решения, правильно ли я вообще думаю.


Ответ

Раскладываем на простые множители НОК. Получаем список множитель-кратность (например, при разложении 12 будет два множителя - 2 с кратностью 2 и 3 с кратностью 1). Назовём его список1. Раскладываем на простые множители имеющееся число (назовём его список2). Далее обрабатываем оба списка, создавая список3.
Если некий множитель отсутствует в список1, но имеется в список2, задача нерешаема. Если кратность множителя в список1 меньше его кратности в список2, задача нерешаема. Если некий множитель имеется в список1, но отсутствует в список2, он помещается в список3 с той же кратностью, что и в список1 Если кратность множителя в список1 больше его кратности в список2, он помещается в список3 с той же кратностью, что и в список1 Если некий множитель имеется в список1 и список2 с одинаковой кратностью, он помещается в список3 с кратностью 0 (ноль).
Перемножая множители из список3 с учётом кратности, получаем минимальное решение. Остальные решения получаем увеличением кратности одного или нескольких множителей в список3, но не превышая их кратности в список1
Всё.

Комментариев нет:

Отправить комментарий