arrays - 给定数组和全互素数组之间的最小距离

Question

我们有以下问题：

让我们称一个数字序列为“ b[1]...b[n] fancy if gcd(b[i], b[j]) = 1for all 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[意思是输入数组可以有值在这个范围内的元素]

我对这个完全没有想法。
我们怎样才能以最优化的方式解决这个问题？

标签： arraysnumbersprimesmathematical-optimization