题意
有n堆石头, 每堆的初始数量为a1,a2,…..,an
Bob每次可以从一堆里拿一块石头放到另一堆中, 问最少操作多少次能够使得每堆石头的数量能被一个数x(x>1)整除, 在这里, 我们默认0能被任何数字整除
思路
先分解质因数, x的取值只可能是石头总和sum的质因数
然后对每个质因数进行操作, 即使每堆石头变成0或者质因数的k(k>=1)倍
先对每堆石头进行处理, 处理为该堆石头的数量与它前一个质因数倍数的差值. ( 当这个数小于质因数, 则算它与0的差值 )
比如一堆石头 1 2 3 4 5, 和为15, 当处理到质因数为3的时候, 把这堆石头预处理为 1 2 0 1 2 (当然这里的0意味着已经是质因数的k倍, 就可以不存了), 然后贪心一下, 对预处理好的数组从大到小排序
这样我们对预处理好的石头堆做一下前缀和处理, 当某一个时刻, 前缀和 == 后缀个数*质因数 - 后缀和 的时候, 前缀和即为当前答案. 这里怎么理解呢? 其实是 : 前面的石堆是用来往外拿, 去补后面的石堆. 那么后缀个数*质因数 - 后缀和也就是把后缀的石堆补到质因数的(k+1)倍 !(之前预处理的是它与质因数k倍的距离)
读题对我们队来说简直是个大坑啊QAQ
The sum of N of all test cases is not exceed 5∗105.
被我们读成了a数组的和不超过5e5, 人家说的是所有test里n的和啊…… 也不知道谁读的, 也不知道咋读的, 三个瓜皮都没看出来读错了??? 赛后被告知怎么还得要long long??? 我们还一lemon逼??? 我佛了
AC代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <set>
#define FRER() freopen("in.txt", "r", stdin)
using namespace std;
typedef long long ll;
const ll maxn = 1e5+5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll a[maxn], b[maxn], res[maxn], pre[maxn];
vector<ll> vec;
set<ll> st;
bool pr[maxn];
ll num;
void prime(){
ll n = 1e5+5;
ll m = sqrt(n+0.5);
memset(pr, 0, sizeof pr);
for(ll i = 2; i <= m; i++)
if(!pr[i])
for(ll j = i*i; j <= n; j+=i)
pr[j] = 1;
for(ll i = 2; i <= n; i++){
if(!pr[i]){
vec.push_back(i);
num++;
}
}
}
ll solve(ll n)
{
st.clear();
for(ll i = 0; i < num; i++){
if(n==1) break;
if(vec[i]*vec[i]>n) {
st.insert(n);
break;
}
while(n%vec[i]==0){
n /= vec[i];
st.insert(vec[i]);
}
}
return (ll)st.size();
}
int main()
{
num = 0;
prime();
//cout << num << endl;
sort(vec.begin(), vec.end());
ll n, T;
scanf("%lld",&T);
while(T--){
scanf("%lld",&n);
ll sum = 0;
for(ll i = 0; i < n; i++){
scanf("%lld",&a[i]);
sum += a[i];
}
ll t = solve(sum);
ll ans = INF;
set<ll>::iterator it = st.begin();
for( ; it!=st.end(); it++){
ll temp = *it;
// cout << "质因数 : " << temp << endl;
ll cnt = 0;
for(ll j = 0; j < n; j++){
if(a[j]%temp == 0) continue;
if(a[j]<temp) b[cnt] = a[j];
else b[cnt] = a[j] % temp;
cnt++;
}
sort(b, b+cnt);
for(ll j = 0; j < cnt; j++){
//cout << b[j] << " ";
pre[j] = j==0 ? b[j] : pre[j-1]+b[j];
}
//cout <<"---- " << endl;
ll sum2 = pre[cnt-1];
ll j = 0;
for(j = 0; j < cnt; j++){
//cout << "----" << endl;
// cout << pre[j] << endl;
// cout << cnt-j-1 << endl;
// cout << (cnt-j-1)*temp-(sum2-pre[j]) << endl;
if(pre[j]==(cnt-j-1)*temp-(sum2-pre[j]))
break;
}
// cout << "j : "<< j << ", ";
//cout << pre[j] << endl;
ans = min(ans, pre[j]);
}
// cout << "ans = ";
printf("%lld
", ans);
}
return 0;
}