题目链接：https://codeforces.com/contest/1305/problem/F 这是一道很神仙的题 算法就是我们一般不常用的随机化
我们发现，这个玩意的操作上线是
n
n
n，只要以
2
2
2作为最终的
G
C
D
GCD
GCD即可
此时，也就是说操作次数
>
=
2
>=2
>=2的数的个数
<
=
n
/
2
<=n/2
<=n/2,于是我们可以想到随机化，我们先打乱整个序列，然后从中选出前
100
100
100个数，认为它们只操作不超过一次。
由于随机选出一个数操作次数大于等于
2
2
2的概率不超过
1
/
2
1/2
1/2，也就是说挂掉的概率大概为
1
2
100
\frac{1}{2^{100}}
21001
最后一点要强调的是，我们随机的时候要打乱序列，否则很可能会像我一样被出题人"善意"的数据卡掉
随机数
5224999
5224999
5224999万岁！！！ 随机数
5224999
5224999
5224999万岁！！！ 随机数
5224999
5224999
5224999万岁！！！
C
o
d
e
Code
Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
using namespace std
;
#define int long long
#define max(a, b) a > b? a : b
#define min(a, b) a < b? a : b
const int MAXN
= 2e5, MAXP
= 1e6;
int a
[MAXN
+ 10], num
[MAXN
+ 10], top
= 0;
int prime
[MAXP
+ 10], vis
[MAXP
+ 10], tot
= 0;
inline int read();
void euler(int n
){
for (register int i
= 2; i
<= n
; ++i
){
if (!vis
[i
]){prime
[++tot
] = i
, vis
[i
] = i
;}
for (register int j
= 1; j
<= tot
&& prime
[j
] * i
<= n
; ++j
){
if (prime
[j
] > vis
[i
]) break;
vis
[i
* prime
[j
]] = prime
[j
];
}
}
}
void get_prime(int n
){
for (register int i
= 1; i
<= tot
&& prime
[i
] * prime
[i
] <= n
; ++i
){
if (n
% prime
[i
] == 0){
if (!vis
[i
]) num
[++top
] = prime
[i
], vis
[i
] = 1;
while (n
% prime
[i
] == 0) n
/= prime
[i
];
}
}
if (n
> 1) num
[++top
] = n
;
}
int get_ans(int x
, int n
){
int ans
= 0;
for (register int i
= 1; i
<= n
; ++i
){
int sum
= min(a
[i
] % x
, x
- a
[i
] % x
);
if (a
[i
] < x
) sum
= x
- a
[i
];
ans
+= sum
;
}
cerr
<< x
<< " " << ans
<< endl
;
return ans
;
}
signed main(){
freopen
("std.in", "r", stdin);
freopen
("std.out", "w", stdout);
srand(time(0) * 5224999);
int n
= read(), ans
= 2e5; euler(1e6);
memset(vis
, 0, sizeof(vis
));
for (register int i
= 1; i
<= n
; ++i
) a
[i
] = read();
random_shuffle(a
+ 1, a
+ n
+ 1); int mx
= min(n
, 100);
for (register int i
= 1; i
<= mx
; ++i
){
get_prime(a
[i
]), get_prime(a
[i
] - 1), get_prime(a
[i
] + 1);
}
for (register int i
= 1; i
<= top
; ++i
)
ans
= min(ans
, get_ans(num
[i
], n
));
printf("%lld\n", ans
);
return 0;
}
inline int read(){
int x
= 0;
char c
= getchar();
while (!isdigit(c
))c
= getchar();
while (isdigit(c
))x
= (x
<< 1) + (x
<< 3) + (c
& 15), c
= getchar();
return x
;
}
