Как найти два числа, если известно их НОД и НОК?

Question

Входные данные В первой строке дано натуральное число A — НОД некоторых двух натуральных чисел( 1 ⩽ A ⩽ 10000 ).

Во второй строке дано натуральное число B — НОК некоторых двух натуральных чисел( 1 ⩽ B ⩽ 10000 ).

Выходные данные Выведите два натуральных числа через пробел (неважно в каком порядке), НОД которых равен A и НОК которых равен B . Если таких чисел не существует, выведите -1.

Answer 1

Начнем с того, что если это числа a и b, то

a*b = НОД*НОК

Кроме того, a = НОД*a1, и b = НОД*b1.

Так что задача - найти такие a1 и b1, у которых НОД=1 (взаимно простые).

a1 = 1 и b1 = НОК/НОД подходят, как одно из решений, так что a = НОД, b = НОК является решением. Прочие можно искать разложением на простые сомножители и перебирать все возможные вариант (а их может оказаться много :)).

Очевидно, что решение существует не для всех с потолка взятых НОД и НОК - как минимум, НОК должно делиться на НОД.

Могут быть и другие решения. Вам нужно найти все решения или любое решение?

Как я понимаю из условия, хватит и одного. Тогда

int GCD, LCM;
cin >> GCD >> LCM;
if (LCM % GCD != 0) cout << -1; 
else cout << GCD << " " << LCM/GCD;

Answer 2

Поскольку

НОК(a, b) = a * b / НОД(a, b)

То сразу можно найти произведение чисел, а дальше надо просто решить в лоб:

перебрать все числа a, b
вычислить НОД(a, b) и проверить на совпадение

Цикл, чтобы работал побыстрее можно сделать так:

mul = lcm / gcd

for a in range(1, mul + 1):
    if mul % a != 0:
        continue

    b = mul // a

    if gcd_func(a, b) == gcd:
        print(a, b)

БЛОГ НА HUSL

Как найти два числа, если известно их НОД и НОК?

Ответы (2 шт):