Найдите максимально возможную НОД для некоторой пары в заданном диапазоне [L, R]

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

При заданном диапазоне от L до R задача состоит в том, чтобы найти максимально возможное значение НОД (X, Y) такое, что X и Y принадлежат заданному диапазону, т. е . L ≤ X < Y ≤ R.

Примеры:

Input: L = 101, R = 139
Output:
34
Explanation:
For X = 102 and Y = 136, the GCD of x and y is 34, which is the maximum possible.

Input: L = 8, R = 14
Output:
7 

Наивный подход: каждая пара, которая может быть сформирована от L до R , может быть повторена с использованием двух вложенных циклов, и может быть найдено максимальное НОД.

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

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

  • Пусть максимальный НОД будет Z, следовательно, X и Y кратны Z . И наоборот, если в сегменте [L, R] есть два или более кратных Z , то (X, Y) можно выбрать так, чтобы НОД (x, y) был максимальным, выбрав последовательные кратные Z в [L, R] .
  • Перейдите от R к 1 и найдите, есть ли у любого из них по крайней мере два кратных в диапазоне [L, R]
  • Кратность Z между L и R можно рассчитать по следующей формуле:
    • Количество кратных Z в [L, R] = Количество кратных Z в [1, R] – Количество кратных Z в [1, L-1]
    • Это можно записать как:
      • Количество кратных Z в [L, R] = пол (R / Z) - пол ((L-1) / Z)
  • Мы можем дополнительно оптимизировать это, ограничив итерацию от R/2 до 1 , поскольку максимально возможный GCD равен R/2 (с кратными R/2 и R).

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

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

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