首先可以知道答案一定 $\le n$，这个界还可以再紧一点，一定 $\le$ 奇数的个数，设为 $t$。
考虑找到所有最终可能的 $\gcd$，随便找一个数 $x$，由于最多 $+t/-t$，因此这个 $x$ 最终只能在 $[a_i-t, a_i+t]$ 这个范围内，因此 $\gcd$ 也只能在这个范围内的数的质因数中。
我们对这个范围做区间筛，即可找到所有的质因数。具体而言，设这个区间为 $[l,r]$，则可能的 $\gcd$（即所有质因数）包括：
1. $2 \sim \sqrt r$ 内的所有质数，称为**小质数**。
2. 对于 $x \in [l,r]$，$x$ 超过 $\sqrt r$ 的质因数，而这个质因数最多只有一个，称为**大质数**。
把这些可能的 $\gcd$ 全部暴力 check，check 的时候剪枝就行了。
看起来复杂度不太对，但是实际上**长得很像答案的 $\gcd$** 最多只有 $12$ 个，其中 $10$ 个是小质数，$2$ 个是相邻的大质数。
```cpp
const int N = 2e5 + 7;
const ll M = 2e6;
int n;
bool v[M|1];
ll a[N];
vector<ll> p, q;
int main() {
for (ll i = 2; i <= M; i++) {
if (v[i]) continue;
p.pb(i);
for (ll j = i * i; j <= M; j += i) v[j] = 1;
}
q = p;
rd(n), rda(a, n);
sort(a + 1, a + n + 1);
ll d = a[1];
for (int i = 2; i <= n; i++) d = __gcd(d, a[i]);
if (d != 1) return print(0), 0;
ll t = 0;
for (int i = 1; i <= n; i++) t += a[i] & 1;
ll l = max(M + 1, a[n] - t), r = a[n] + t;
map<ll, ll> w;
for (ll i = l; i <= r; i++) w[i] = i;
for (ll x : p)
for (ll i = l / x * x; i <= r; i += x)
if (i >= l) while (!(w[i] % x)) w[i] /= x;
for (ll i = l; i <= r; i++)
if (w[i] > M) q.pb(w[i]);
for (ll x : q) {
if (x == 2) continue;
ll o = 0;
for (int i = 1; i <= n; i++) {
o += min(a[i] < x ? x : a[i] % x, x - a[i] % x);
if (o >= t) break;
}
t = min(t, o);
}
print(t);
return 0;
}
```