Создайте массив с элементами в заданном диапазоне и отдельным НОД каждого элемента с его индексом
Даны 3 целых числа N, L и R. Задача состоит в том, чтобы построить массив A[] из N целых чисел, такой что:
- Каждый элемент массива находится в диапазоне [L, R].
- НОД(i, A[i]) различны для всех элементов.
Примеры :
Input : N = 5, L = 1, R = 5
Output : {1, 2, 3, 4, 5}
Explanation : It can be seen that each element is in the range [1, 5].
Also, for i = 1, GCD(1, 1)=1, for i = 2, GCD(2, 2) = 2, for i = 3,
GCD(3, 3) = 3, for i = 4, GCD(4, 4) = 4 and for i = 5, GCD(5, 5) = 5.
Hence, all of these are distinct.Input : N = 10, L = 30, R = 35
Output : -1
Explanation : It is not possible to construct an array
satisfying the given conditions.
Подход: Подход к проблеме основан на следующем наблюдении.
To satisfy the given conditions, we will have to assure GCD(i, A[i]) = i, for each index of the array from 1 to N.
The idea is to find the smallest possible element with gcd(i, A[i]) = i, larger than or equal to L for each i, and if that element is smaller than equal to R, then we append it, otherwise we return -1(means not possible).
Проблема может быть решена следующим подходом:
- Итерация от i = 1 до N .
- Для каждого i найдите минимальное кратное i , которое строго больше L − 1 .
- Проверьте, меньше ли это кратное R или равно ему.
- Если это так, то это кратное будет i- м элементом массива.
- В противном случае построение массива было бы невозможно.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность : O(N)
Вспомогательное пространство : O(N)