提供一种做法

思路

假设当前已经合并好了

有结论

所有 有 货物的仓库的 货物数的 gcd 即为 答案

如何证明？

• 因为我们要求分成若干相等货物数的箱子

• 所以对于一个仓库，这个箱子数肯定要整除仓库所含货物数

• 由题，则任意两个仓库，它们分好后每个箱子的货物数相等

• 我们记为 $w$

• 若 $w≠gcd$ ,那么 $w<gcd$

• 因为若 $w>gcd$ 此时必然出现某个仓库的货物数无法被整除，不合法

• 而当$w<gcd$ 时，此时不满足题目要求最大，不符合要求不合法

我们会发现因为有连对转移，这个gcd是在变动，无法求得最大

假定一个 $gcd$ 为我们要求答案

我们对它进行唯一分解

得到 $a^{p_1}_1\times a^{p_2}_2\times \dots a^{p_k}_k$

观察题目条件， $a_i < 10^6$ ,那么两个仓库连在一起为 $10^6 \times 2$

我们可以枚举 $2\times 10^6$ 的质数

然后判该质数是否合法，再判该质数的多少幂次合法(可以二分)，把该质数纳入候选集

然后对于 $2\times 10^6$ 的所有数，我们看看当前数对于候选集依次整除后是否结果为1

以及整除后每个质数的幂次是否在限定范围内

然后把该数压入大根堆或可变长数组，排序后从大到小试，第一个可行即为答案

值得一提的是判别，即 $check$ ，因为如果一个仓库整除不了，一定会找一个也整除不了的（为什么？）

我们从左往右递推（当前不合法只考虑右边不合法,为什么？）

线性，并且加入剪枝优化时间复杂度，可以跑得很快

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll =long long;
using pii =pair<int,int>;
const int N=2e5+9,M=2e6+9,inf=1e9+9;
const ll INF=1e18+9;
int n,B; 
int a[N];
vector<int> prim,ve,re;
bool vis[M];
int po[M];//幂次积的合法值 

bool check(int p){
    int poi=1;
    ll sum=0;
    while(poi<=n){
//        cout<<poi<<endl;
        if(a[poi]%p!=0){
            if(poi==n){return false;}
            else {
                int nx=poi+1;
                if(a[nx]%p==0||(a[nx]+a[poi])%p!=0){return false;}
                sum+=min(a[nx]%p,a[poi]%p);
                poi=nx+1;
                if(sum>B)return false;
            }
        }else poi++;
    }
    return true;
}

bool ck(int x){//对于非质数的判别
    for( int k:ve){
        int cnt=0;
        while(x!=0&&x%k==0){
            x=x/k;
            cnt++;
        }
        if(cnt>po[k])return false;
    }
    if(x!=1)return false;
    return true;
}

void solved(){
    cin>>n>>B;
    int mx=0;
    for(int i=1;i<=n;i++)cin>>a[i],mx=max(mx,a[i]);
    int m=mx*2;//最大的可能值
    for(int i=2;i<=m;i++){
        if(!vis[i]){
            prim.push_back(i);
            for(int j=i+i;j<=m;j+=i)vis[j]=true;
        }//埃氏筛 
    }
    for(int x:prim)if(check(x))ve.push_back(x);
    for(int x:ve){
        int cnt=0;int las=x;
        while(check(las)){//可以使用二分优化
            cnt++;
            las=las*x;
            if(las>m)break;
        }
        po[x]=las;
    }
    for(int i=2;i<=m;i++){
        if(!vis[i]&&po[i]!=0)re.push_back(i);
        else if(ck(i))re.push_back(i);
    }
    sort(re.begin(),re.end());reverse(re.begin(),re.end());
    for(int x:re){if(check(x)){cout<<x;return;}}
    cout<<1;
} 

相邻调拨：解法与部分分

先不要考虑怎样搬．如果每个仓库最后都能装成容量为 $k$ 的整箱，那么总货物量 $S$ 也一定是 $k$ 的倍数．因此只需要检查 $S$ 的约数．

固定 $k$，从左向右看第一个不能整除 $k$ 的仓库 $i$．它必须参与搬运，又不能跟一个已经整除 $k$ 的仓库配对：那样两个仓库的总数不能整除 $k$，不可能都装完．左边其他仓库已经处理过，所以它只能和 $i+1$ 配对．这一步不是随意选的贪心，而是被条件强迫的．

如果 $i$ 已经是最后一个，或者 $a_i+a_{i+1}$ 不能整除 $k$，这个 $k$ 就不可行．否则令 $r=a_i\bmod k$，另一边的余数必为 $k-r$．

可以把左边多出的 $r$ 件搬到右边，也可以从右边搬 $k-r$ 件过来，使左边凑满下一箱．两边都有足够的货物完成对应操作，所以最小搬运量恰为 $\min(r,k-r)$．比这更远的倍数只会搬得更多．

检查完这一对后跳过两个仓库．各对互不相交，费用可以相加；总费用不超过 $B$ 就可行．按约数从大到小检查，第一个可行的就是答案．

时间 $O(\sqrt S+n\tau(S))$，空间 $O(n+\tau(S))$．其中 $\tau(S)$ 是约数个数．

部分分

实现时不要把余数排序：相邻关系是本题的约束，不能丢．所有初始数量均为正，总和不为零，所以最大箱容量有界．

总和较大时的实现

完整数据不限制 $S\le10^6$，由 $n$ 和 $a_i$ 的上界可知 $S\le2\times10^{11}$．总和、约数、枚举约数时的乘积以及累计搬运量均使用 long long．不能再枚举 $1,\ldots,S$ 的所有整数容量．

仍可枚举 $S$ 的约数．虽然 $S$ 变大，但大多数候选在开头就会失败：能够处理完第一个仓库的容量，一定整除 $a_1$ 或 $a_1+a_2$．因此带提前失败的扫描可以更精确地界为 $O(\sqrt S+\tau(S)\log\tau(S)+n(\tau(a_1)+\tau(a_1+a_2)))$，这里假设 $n\ge2$；$n=1$ 可直接输出 $a_1$．

也可以一开始就枚举 $a_1$ 与 $a_1+a_2$ 的约数，去重后按从大到小判定，完全不依赖总和大小．

参考程序

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
ll solve(const vector<int>& a, ll b) {
    ll s = 0;
    for (int x : a) s += x;
    vector<ll> ds;
    for (ll d = 1; d * d <= s; ++d) if (s % d == 0) {
        ds.push_back(d);
        if (d * d != s) ds.push_back(s / d);
    }
    sort(ds.rbegin(), ds.rend());
    for (ll k : ds) {
        ll cost = 0;
        bool ok = true;
        for (int i = 0; i < (int)a.size(); ++i) {
            ll r = a[i] % k;
            if (!r) continue;
            if (i + 1 == (int)a.size() || (a[i] + a[i + 1]) % k) {
                ok = false;
                break;
            }
            cost += min(r, k - r);
            if (cost > b) { ok = false; break; }
            ++i;
        }
        if (ok) return k;
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
#ifdef SELF_TEST_BATCH
    cin >> t;
#endif
    while (t--) {
        int n; ll b;
        cin >> n >> b;
        vector<int> a(n);
        for (int& x : a) cin >> x;
        cout << solve(a,b) << '\n';
    }
}