题意
有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#include #include #include #include #include #include #include #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 vec;set 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 ::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]