Минимум и максимум LCM среди всех пар (i, j) в диапазоне [L, R]

Даны два положительных целых числа L и R , представляющие диапазон. Задача состоит в том, чтобы найти минимальное и максимально возможное НОК любой пары (i, j) в диапазоне [L, R] такое, что L ≤ i < j ≤ R .

Примеры:

Input: L = 2, R = 6
Output: 4 30
Explanations: Following are the pairs with minimum and maximum LCM in range [2, 6].
Minimum LCM –> (2, 4) = 4
Maximum LCM –> (5, 6) = 30

Input: L = 5, R = 93
Output: 10 8556

Подход: Эту проблему можно решить с помощью простой математики. Выполните следующие шаги, чтобы решить данную проблему.

Для минимального LCM,

• Одно число наверняка будет минимальным числом в диапазоне [L, R] .
• Подберите числа таким образом, чтобы одно было множителем другого.
• Единственное число с L, которое дает минимальный LCM, — это 2*L .
• Проверить, если 2*L <= R
  • Если да, минимальный LCM будет 2*L
  • В противном случае минимальный LCM будет равен L*(L+1) .

Для максимального LCM,

• Одно число наверняка будет максимальным числом в диапазоне [L, R] , то есть R .
• Выберите второе число так, чтобы оно было взаимно простым с R, а произведение обоих было максимальным.
• R и R-1 всегда будут взаимно просты, если R!=2 .
• Следовательно, R*(R-1) будет давать максимальный LCM.

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

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