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

264

22 июня 2018, 18:40

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

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

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

Answer 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.

Всё.

Answer 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

<script src="https://cdn.rawgit.com/brython-dev/brython/3.4.0/www/src/brython.js"></script><body onload="brython()"><script type="text/python"> 
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 
     
def gcd(a, b): 
    while b: 
        a, b = b, a%b 
    return a 
     
def lcm(a, b): 
    return a * b // gcd(a, b) 
     
from browser import document 
@document["mybutton"].bind("click") 
def on_click(event): 
    b = int(document["b"].value) 
    lcm_ = int(document["lcm"].value) 
    a_ = a(b, lcm_) 
    assert lcm_ == lcm(a_, b) 
    print(f"a={a_}, b={b}, lcm={lcm(a_,b)}") 
on_click('dummy on start')     
</script><label for="b">b:&nbsp;</label><input id="b" value="16"> <label for="lcm">lcm:&nbsp;</label><input id="lcm" value="80"> <button id="mybutton">Найти a</button></body>

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

>>> 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)

Answer 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;
}