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

#cpp #python #алгоритм

Не могу понять, как эту задачу можно решить без "тупого" перебора чисел от НОК/данное
число, до самого НОК. Число, которое нужно найти, должно быть минимальным подходящим
к данным.

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

Перебором нельзя т.к. числа будут огромные. Написать код не прошу, просто интересна
сама суть решения, правильно ли я вообще думаю.
    

Ответы

Ответ 1

Раскладываем на простые множители НОК. Получаем список множитель-кратность (например,
при разложении 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.

Всё.


Ответ 2

Если любое решение интересует, то тривиальным (наибольшим) ответом является сам НОК,
т.к. max(max(e, d), d) == max(e, d), см. каноническое разложение. Если известно b и
lcm(a, b), и требуется любое a найти, то ответ: 
a = lcm(a, b) то есть:

lcm(a, b) == lcm(lcm(a, b), b)


Чтобы минимальное из возможных решений найти, в разложении на простые множители,
кратность простых чисел в наименьшем общем кратном (НОК) равна максимуму кратности
обоих чисел (см. каноническое разложение), поэтому кратность в искомом (минимальном
среди возможно нескольких решений) либо равна кратности в НОК, либо нулю, если кратность
в первом числе равна кратности в НОК:



# a = p**d * ...; b = p**e * ...; lcm(a, b) = p**m ... where m = max(d, e)
assert e <= m
d = 0 if m == e else m


Для маленьких чисел, можно находить простые множители перебором всех делителей:

def a(b, lcm):
    """Find *a* given *lcm(a, b)* and *b*."""
    a = 1
    p = 2  # prime factor
    while p * p <= b:
        # find multiplicity of p in b
        e = 0  # b = p**e * ...
        while b % p == 0:  # found prime factor
            e += 1  # increase multiplicity
            b //= p
            assert lcm % p == 0
            lcm //= p

        # find multiplicity of p in lcm
        # lcm = p**m * ...
        m = e
        while lcm % p == 0:  # d = max(d, e)
            m += 1  # increase multiplicity
            lcm //= p

        # a = p**d * ...
        if m > e:  # max(d, e) > e
            a *= p**m  # d == m
        else:  # d = 0
            assert m == e
        p += 1
    assert lcm % b == 0  # last prime factor or 1
    if lcm % b**2 != 0:  # e = max(d, e)
        lcm //= b
    return a * lcm




b:  lcm:  




Примеры использования:

>>> a(b=28, lcm=84)
3
>>> a(b=21, lcm=84)
4
>>> lcm(a(b=3, lcm=84), 3)
84
>>> a(b=2, lcm=4)
4
>>> a(b=4, lcm=4)
1
>>> a(b=20, lcm=80)
16
>>> a(b=16, lcm=80)
5
>>> a(b=1, lcm=lcm(2, 1))
2
>>> a(b=2, lcm=lcm(2, 1))
1
>>> lcm(a(b=2, lcm=lcm(2, 1)), 2)
2


где lcm(a, b):

from math import gcd

def lcm(a, b):
    return a * b // gcd(a, b)


Ответ 3

Решение без явной факторизации. Сложность не больше чем число простых делителей числа
(а в среднем значительно быстрее). 

Пусть у нас есть равенство НОК = а*b/НОД(a,b) Или НОК/а = b/НОД(a,b). Нам нужно минимизировать
b. Левая часть дана по условию. Понятно что минимум будет, при минимуме НОД. Пусть
он равен 1. Тогда b1 = НОК/а. Любое b будет делиться на b1 (думаю очевидно) и может
быть записано как b1 * c1. Дальше. c1 будет делиться на НОД(a,b1). Продолжать итерационно
пока не остановится процесс. 

Код короче чем объяснение =) 

long calc(long nok, long first){
    if (nok % first != 0)
        return -1; //wrong input
    long res = nok/first;
    long g = 1;
    long tmp;
    while ( (tmp = gcd(first, res)) != g){
        g = tmp;
        res = nok/first * g;
    }
    return res;
}


Запускаемый пример с тестированием https://ideone.com/HdBNgj