Найдите две пары, НОД одной из которых совпадает с НОК другой, а сумма равна N.

Опубликовано: 19 Сентября, 2022

Для заданного целого числа N задача состоит в том, чтобы найти две пары положительных целых чисел, такие что НОД первой пары совпадает с НОК второй пары, а сумма значений равна N.

Примечание. Если возможно несколько выходных данных, распечатайте любой из них.

Примеры:

Input: N = 9
Output: 6 1 1 1
Explanation: The GCD(6, 1) = 1 and LCM(1, 1) = 1, GCD is equal to LCM.
The sum of all numbers (6 + 1 + 1 + 1) = 9

Input: N = 3
Output: -1
Explanation: We can’t give positive integer values to all the four values.

Подход: Подход к проблеме основан на следующем наблюдении:

GCD of any number with 1 is always 1 and LCM of 1 and 1 will always be 1. 
So, fix first number of GCD N-3 and second as 1 and all other numbers of LCM as 1 and 1. 
So at the end the sum of all numbers (N-3 + 1 + 1 + 1) will be N and GCD (N-3, 1) will be equal to LCM(1, 1).

Выполните шаги, указанные ниже, чтобы реализовать наблюдение:

  • Если N < 4 , то найти четыре таких значения невозможно.
  • В противном случае найдите четыре значения в соответствии с приведенным выше наблюдением.

Ниже приведен код для вышеуказанной реализации:

Временная сложность: O(1)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ