1

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

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

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

2 ответа 2

4

Начнем с того, что если это числа 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;
2
  • Большое спасибо, всё верно, требуется любое решение 24 окт 2020 в 15:01
  • Ну, осталось выбрать, какое из решений принять :)
    – Harry
    24 окт 2020 в 15:17
1

Поскольку

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

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

  1. перебрать все числа a, b

  2. вычислить НОД(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)
1
  • Большое спасибо, помогли 24 окт 2020 в 15:01

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.