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
|
using namespace std;
#define endl "n"
const int maxn = 1e5 + 5;
int n; long long a[maxn]; int contain[maxn];
long long calc(long long x) { for (int i = 1; i < x; i++) { contain[i] = 0; } long long sum = 0; for (int i = 1; i <= n; i++) { contain[a[i] % x]++; sum += a[i] % x; } long long res = 0; for (int i = x - 1, j = 1; i > 0 && sum > 0; i--, j++) { for (; sum > 0 && contain[i]; contain[i]--) { res += j; sum -= x; if (sum <= 0) break; } } return res; }
int () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T; cin >> T; while (T--) { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } long long sum = 0; for (int i = 1; i <= n; i++) { sum += a[i]; }
long long res = 0x3f3f3f3f3f3f3f3f; for (int i = 2; 1ll * i * i <= sum; i++) { if (sum % i == 0) { res = min(res, calc(i)); while (sum % i == 0) sum /= i; } } if (sum > 0 && sum < maxn) res = min(res, calc(sum));
if (res != 0x3f3f3f3f3f3f3f3f) cout << res << endl; else cout << sum - *max_element(a + 1, a + 1 + n) << endl; } }
|
近期评论