Найти НОД каждого элемента массива B[], добавленного ко всем элементам массива A[]
Даны два массива a[] и b[] длины n и m соответственно, задача состоит в том, чтобы найти наибольший общий делитель (НОД) {a[0] + b[i], a[1] + b[i], a[2] + b[i], …, a[n – 1] + b[i]} (где 0 <= i <= m – 1).
Input: a[] = {1, 10, 22, 64}, b[] = {5, 23, 14, 13}
Output: 3 3 3 1
Explanation:
- i = 1 : GCD(5+1, 5+10, 5+22, 5+64) = GCD(6, 15, 27, 69) = 3
- i = 2 : GCD(23+1, 23+10, 23+22, 23+64) = GCD(24, 33, 45, 87) = 3
- i = 3 : GCD(14+1, 14+10, 14+22, 14+64) = GCD(15, 24, 36, 78) = 3
- i = 4 : GCD(13+1, 13+10, 13+22, 13+64) = GCD(14, 23, 35, 77) = 1
Input: a[] = {12, 30}, b[] = {5, 23, 14, 13}
Output: 1 1 2 1
Подход: проблема может быть эффективно решена с использованием свойства евклидова алгоритма НОД, который утверждает НОД(x, y) = GCD(x−y, y) . То же самое относится к множеству аргументов НОД(x, y, z, …) = НОД(x−y. y, z, …) . Применяя это свойство, проблема может быть решена с помощью шагов, приведенных ниже:
- Чтобы вычислить НОД(a[0] + b[i], …, a[n – 1] + b[i]) , вычтите a[0] + b[i] из всех остальных аргументов.
- Теперь НОД ( a[0] + b[i], …, a[n - 1] + b[i]) = GCD ( a[0] + b[i], a[1] - a[0] , …, а[n – 1] − а[0]) .
- Найдите G = GCD(a[1] − a[0], …, a[n – 1] − a[0]) , тогда gcd для любого i можно вычислить как GCD(a[0] + b[i ], г) .
- Перебрать все возможные значения i от 1 до m и вычислить gcd как G(i) = GCD(a[1]+b[i], G) и вывести G(i).
Ниже приведена реализация описанного выше подхода.
Временная сложность: O((N + M) * log(X)), где M — максимальный элемент в массиве a[].
Вспомогательное пространство: O(1)