查找数组中一对元素的最小 GCD

Question

给定一个元素数组，我必须找到可能的最小 GCD在任意两对数组之间，时间复杂度最低。

例

输入

arr=[7,3,14,9,6]

约束

N= 10^ 5

输出

1

解释

min gcd can be of pair(7,3)

我的天真解决方案- O(n^2) 糟糕的天真蛮力

int ans=INT_MAX;
for (int i = 0; i < n; ++i)
{
for(int j=i+1; j<n; j++){
int g= __gcd(arr[i],arr[j]);
ans=min(ans,g);
}
}
return ans;

你能建议一种时间复杂度最小的更好方法吗？

Answer 1

此解决方案在时间 O(n + h log h 中工作)，其中 h 是数组中的最大数字。让我们解决一个更难的问题：对于每个 x <= h，计算无序对 (i， j) 的数量 d[x]，使得 0 <= i， j

莫比乌斯反演可用于解决以下问题：你需要找到一个数组 y，但你得到一个数组 z，使得 z[k] = y[k] + y[2*k] + y[3*k] + ....令人惊讶的是，它可以就地工作，而且只有三行代码！

这正是我们所需要的，首先我们要找到有序对(i， j)的数量，使得d[x]除以GCD(a[i]，a[j])，但是我们需要有序对的数量(i，j)，使得d[x]是GCD(a[i]，a[j])。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
int n, h = 0;
cin >> n;
vector<int> a(n);
for (int& x : a) {
cin >> x;
h = max(h, x);
}
h++;
vector<ll> c(h), d(h);
for (int x : a)
c[x]++;
for (int i=1; i<h; i++)
for (int j=i; j<h; j+=i)
d[i] += c[j];
// now, d[x] = no. of indices i such that x divides a[i] 
for (int i=1; i<h; i++)
d[i] *= d[i];
// now, d[x] = number of pairs of indices (i, j) such that
// x divides a[i] and a[j] (just square the previous d)
// equiv. x divides GCD(a[i], a[j])
// apply Mobius inversion to get proper values of d
for (int i=h-1; i>0; i--)
for (int j=2*i; j<h; j+=i)
d[i] -= d[j];
for (int i=1; i<h; i++) {
if (d[i]) {
cout << i << 'n';
return 0;
}
}
}