У нас есть следующая проблема:
Давайте назовем последовательность чисел b[1]...b[n] fancy если gcd(b[i], b[j]) = 1 для всех 1 <= i < j <= n. (имеется в виду всеэлементы массива взаимно просты друг с другом).
При заданной последовательности чисел a[1], a[2], ..., a[n], каково минимально возможное значение abs(a[1]-b[1]) + abs(a[2]-b[2]) + ... + abs(a[n]-b[n]), где b[1]...b[n] причудливая последовательность?
ПРИМЕР:
Вход - [1, 1, 1, 1, 1]
Выход - 0
Объяснение : [1, 1, 1, 1, 1] сама по себе является «причудливой» последовательностью, поэтому минимально возможное расстояние равно 0.
Ввод - [1, 6, 4, 2, 8]
Вывод - 3
Объяснение - Одна из оптимальных "причудливых" последовательностей - [1, 5, 3, 1, 8].
distance([1, 6, 4, 2, 8], [1, 5, 3, 1, 8]) = | 1-1 |+ | 6-5 |+ | 4-3 |+ | 2-1 |+ | 8-8 |= 3.
Вход - [1, 2, 4]
Выход - 1
Пояснение - Нулевое расстояние равноневозможно, потому что [1, 2, 4] не является «причудливым».
Одна из оптимальных «причудливых» последовательностей - это [1, 2, 3].
distance([1, 2, 4], [1, 2, 3]) = | 1-1 |+ | 2-2 |+ | 4-3 |= 1.
Ограничения
1 ≤ n ≤ 10^2 [Размер массива] 1 ≤ arr[i] ≤ 30 [То есть входной массив может иметь элементы со значениямив этом диапазоне]
У меня совершенно нет идей по этому вопросу.
Как мы можем решить это наиболее оптимальным способом?