11260. Модифицированный НОД

Найдите наибольший общий делитель d двух целых чисел a и b, принадлежащий отрезку целых чисел [low, high] (low ≤ high), то есть такой, что low ≤ d ≤ high.

Может получиться, что в заданном отрезке нет общих делителей.

Даны два целых числа a и b, далее следует n запросов. Каждый запрос – это некоторый отрезок [low, high]. Напишите программу, которая обработает все заданные запросы.

Вход. В первой строке записано два целых числа a и b (1 ≤ a, b ≤ 10⁹). Во второй строке содержится количество запросов n (1 ≤ n ≤ 10⁴). Далее следует n строк. Каждая строка содержит один запрос – два целых числа low и high (1 ≤ low ≤ high ≤ 10⁹).

Выход. Выведите n строк, i-ая из которых должна содержать ответ на i-ый запрос. Если в данном отрезке общих делителей нет, выведите -1.

Пример входа	Пример выхода
9 27 3 1 5 10 11 9 11	3 -1 9

РЕШЕНИЕ

НОД

Анализ алгоритма

Вычислим d = НОД(a, b). Разложим число d на делители. Далее для каждого запроса среди делителей d следует найти наибольший, который принадлежит отрезку [low, high].

Пример

Вычислим d = НОД(9, 27) = 9. Делителями числа 9 будут: 1, 3, 9.

· На отрезке [1; 5] наибольшим делителем будет 3;

· На отрезке [10; 11] делителей нет;

· На отрезке [9; 11] наибольшим делителем будет 9;

Реализация алгоритма

Функция gcd вычисляет НОД чисел a и b.

int gcd(int a, int b)

{

return (!b) ? a : gcd(b, a % b);

}

Основная часть программы. Читаем входные данные.

scanf("%d %d", &a, &b);

Вычисляем d = НОД(a, b).

d = gcd(a, b);

Разложим число d на делители. Занесем делители в массив v.

for (i = 1; i * i < d; i++)

if (d % i == 0)

{

v.push_back(i);

v.push_back(d / i);

}

if (i * i == d) v.push_back(i);

Читаем количество запросов n.

scanf("%d", &n);

for (i = 0; i < n; i++)

{

Читаем запрос – отрезок [low, high].

scanf("%d %d", &low, &high);

res = -1;

Перебираем в массиве v делители числа d. Находим наибольший делитель, принадлежащий промежутку [low, high].

for (j = 0; j < v.size(); j++)

if (v[j] >= low && v[j] <= high)

res = max(res, v[j]);

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

printf("%d\n", res);

}