题目链接：https://codeforces.com/contest/1305/problem/F。
奇怪的题。。
显然答案最大是 $n$ ，因为我们可以把所有奇数搞成偶数。
所以可以发现一个事，如果 $\gcd$ 是其他数的话，那么必然最多只有 $n/2$ 个操作大于一次的。
如果我们随机一个位置 $a_x$ ，然后暴力找出 $a_x-1,a_x,a_x+1$ 的所有质因子，去 $O(n)$ 更新答案，这样正确的概率是 $0.5$。
如果我们重复很多次，正确的概率就很大了。
单次复杂度 $O(\sqrt v+n)$，做个 $30$ 次就能过了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include<bits/stdc++.h>
using namespace std;
#define int long long
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define data asd09123jdf02i3h
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
int n,a[maxn],ans=1e9;
map<int,int > s;
void gao(int x) {
if(s[x]) return ;
if(x<2) return ;
s[x]=1;int res=0;
for(int i=1;i<=n;i++) {
res+=min(a[i]>=x?a[i]%x:(int)1e9,x-a[i]%x);
if(res>=ans) return ;
}
ans=min(ans,res);
}
void check(int x) {
for(int i=2;i*i<=x;i++) {
if(x%i) continue;
gao(i);
while(x%i==0) x/=i;
}
if(x!=1) gao(x);
}
void solve() {
int x=rand()*rand()%n+1;
check(a[x]),check(a[x]+1),check(a[x]-1);
}
signed main() {
read(n);srand(time(0));
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=30;i++) solve();
write(ans);
return 0;
}
|