题解：P12431 [BalticOI 2025] Gingerbread

· · 题解

先把 ans=0 判了。

先给 a 排个序，然后考虑 \gcd 的性质，把 a 替换成它的差分。这时候的操作相当于 a_i\gets a_i+1,a_{i+1}\gets a_{i+1}-1。这时候 \sum a_i 是 O(V) 的。

有这样的结论：我们只要找到两个非空的无交的子序列且它们的和相同，那么 ans=1。证明就是找到这两个子序列中最靠后的那个，利用操作把它 +1，此时的 \gcd 已经是 1 了。

由抽屉原理可知，当 2^n>V 时，ans=1。

所以我们只要考虑 n\le 23 的情况，这时候直接从小到大枚举答案然后爆搜即可，复杂度不是很清楚，反正跑得很快，也完全卡不满。（其实由于上面的分析，n>23 时也可以直接爆搜，不过无所谓了。并且实测这个 n 的上界看起来是 \omega(n) 级别的）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int p[1000005],n,g;
void dfs(int x,int y,int now,int g){
    if(x==n){
        if(__gcd(g,p[x]+y-now)==1) cout<<y<<'\n',exit(0);
        return ;
    }
    for(int i=0;i<=y-now;i++)
        dfs(x+1,y,now+i,__gcd(g,p[x]+i));
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i],g=__gcd(g,p[i]);
    if(g==1) return cout<<"0\n",0;
    if(n>23) return cout<<"1\n",0;
    for(int i=1;;i++)
        dfs(1,i,0,0);
    return 0;
}