A Simple Stone Game
比赛时疯狂写错，赛后发现一开始就漏判一个条件，还是得好好读题。
题目：
给你 n 个数，每一次移动可以在一个数上+1，另外一个数上 -1。问最小移动几次使得他们有一个大于1的公因子。把 0 看成任意数的倍数。
解题思路：
把这 n 个数的总和sum计算出来，最后的公因子一定是这个sum的质因子。素数筛打一个表就行。
枚举所有sum的质因子，每个数对这个质因子取模，排序。接下来简单的贪心，把小的往最后移动就行，更新答案。
注意sum没有质因子的情况。然后就是把所有数移动到一起。答案就是 sum - 最大的数。
代码：
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <fstream>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 1e6 + 5;
const int M = 6e5 + 5;
int t;
ll a[N], n, Max;
vector <ll> V;
int v[M], prime[M], tot;
void prime1(int n){
memset(v, 0, sizeof(v));
for(int i = 2; i <= n; i++){
if(v[i] == 0){
v[i] = i; prime[++tot] = i;
}
for(int j = 1; j <= tot; j++){
if(prime[j] > v[i] || prime[j] * i > n) break;
v[i* prime[j]] = prime[j];
}
}
}
ll sum;
int cmd(ll a,ll b){
return a>b;
}
int main()
{
ll maxnum = -1e18;
prime1(M - 10);
scanf("%d", &t);
for(int ca = 1; ca <= t; ca++){
V.clear();
sum = 0;
Max = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
sum += a[i];
Max = max(Max, a[i]);
}
for(int i = 1; i <= tot; i++){
if(sum % prime[i] == 0) {
V.push_back(prime[i]);
}
}
vector<ll> d; d.clear();
ll ans = sum - Max, sum=0;
for(int j = 0; j < V.size(); j++){
sum=0;
d.clear();
for(int i=1;i<=n;i++){
d.push_back(a[i]%V[j]);
}
sort(d.begin(),d.end());
int l = 0, r = n - 1;
ll tmp = 0;
while(l <= r){
if(d[l] == 0) {
l++;
continue;
}
if(d[r] == 0){
r--;continue;
}
if(d[l] > V[j] - d[r]){
d[l] -= (V[j] - d[r]);
tmp+=(V[j] - d[r]);
r--;
}
else if(d[r] == V[j] - d[l]){
tmp += d[l];
l++, r--;
}
else{
tmp += d[l];
d[r] += d[l];
l++;
}
}
ans=min(ans,tmp);
}
printf("%lld\n", ans);
}
return 0;
}
|
