[AGC057D] Sum Avoidance

原因是如果 (a+b notin B)，则 (n-(a+b))，一定在 (A)中，那么 (a,b,n-(a+b)) 同时在集合 (A) 中，显然不满足条件。

考虑满足该性质的集合 (B) 及对应的 (A)，当它不合法，即 (A) 中的数多次相加能拼成 (S) 时，若拼成 (S) 的数中有一个大于等于 (dfrac{S}{2})（即在集合 (A) 但不在集合 (B) 中） ，则这种情况必定不满足性质1，所以我们只需要考虑集合 (B) 是否合法即可。

那么接下来就是构造了，由于我们要构造字典序最小的 (A) ，所以只需从小往大依次枚举每个数，尝试贪心的将其加入 (B) ，最后得到的 (B) 及其对应的 (A) 就是我们所需要的集合 (A) 了。

加入数时有两种情况：

1.该数能被已经在 (B) 中的数组合出，那么这个数必须加，显然加入它之后集合仍旧合法。

2.当非第一种情况时，若加入该数不会使集合 (B) 不合法，加入该数。

我们设第一个加入集合 (B) 的数为 (d) ，容易发现，(d) 一定是最小的与 (S) 互质的数，并且在此之后每当我们用第 (2) 种方式加入新数时，该数一定与已经在集合中的所有数模 (d) 不同余（同余的话可以由已经在集合中的同余的数和若干个 (d) 组合出）。也就是说，以第二种方式加入的数最多只有 (d) 个。

接下来就来到了同余最短路的相关部分，考虑对于每个 (iin{0,1,···,d-1}) 记录一个 (f_i) 表示已经在 (B) 的数可以构造出的 (equiv i (mod d ))的最小值。

显然，(f) 不会被第一种情况加入的数影响，且最后由 (f) 可以得到整个 (B) 集合（下文讲具体方法）。

先考虑以第二种方式加入一个数 (v equiv x (mod d))，首先一定有 (f_x>v) （否则就是以第一种方式加入了），可以通过枚举加入的 (v) 用了多少次更新 (f) 数组，即:

一个数(v)能被加入当且仅当 (f_x>v) 且加入后 (f_{S mod d}>S)。我们不妨枚举 (x)，容易发现，对于每个 (x) ，加入的合法的 (v) 有其下界 (dn) ，大于等于 (dn) 且 (equiv x(mod d)) 且小于 (f_x) 的数均可加入，从而可以得到当前 (x) 下第一个能加入的数。（当然也可能根本不存在能加入的数）

于是我们可以对每一个 (x) 找到其能加的数，取其中最小的就是下一个能加的数，重复至多 (d) 次即可得到最终的 (f) 数组。

接下来就可以还原 (B) 了，若一个数 (tin B)，当且仅当 (t 且 (tge f_{t mod d})。

此时容易(O(d))求得 (B) 集合内小于等于某个数的元素个数，于是可以二分求得最终答案。复杂度为 (O(d log S))，若答案(> frac{S}{2})，也可以反向类似二分。

考虑 (d) 的范围，容易发现 (d) 在 (10^{18}) 次以内最大为 (43) （(lcm(1,2,···,43)geq 10^{18})）。而事实上，(d=O(log S))

#include 
#define N 50
#define M 2000010
#define pii pair
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long
//#define MOD
#define INF 1061109567
#define int_edge int to[M],nxt[M],head[N],cnt=0;
using namespace std;
int S,k,d,f[N],in[N];
//int_edge;void add_edge(int x,int y ){to[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;}
//int_edge;int val[M];void add_edge(int x,int y,int z){to[++cnt]=y;val[cnt]=z;nxt[cnt]=head[x];head[x]=cnt;}
int check(int nw){
    int tmp=0;
    for(int i=0;i=f[i])tmp+=(nw-f[i])/d+1;
    return tmp; 
}
queueq;
void spfa(int nw){
    for(int i=0;if[u]+nw){f[v]=f[u]+nw;if(!in[v])q.push(v),in[v]=1;}
    }
}
int solve(){
    scanf("%lld %lld",&S,&k);
    if(k>(S-1)/2)return -1;
    if(S==3)return 2;
    if(S==4)return 3;
    if(S==6)return k+3;//d>=S/2
    d=1;while(S%d==0)d++;
    for(int i=1;i=S/2)break;
        spfa(v);//更新f
    }
    int l=1,r=S/2,ans=-1;
    while(l=k+1)ans=mid,r=mid-1;//注意此处由于算入了0所以要与k+1相比
            else l=mid+1;
    }
    if(ans!=-1)return ans;
    l=1,r=S/2,k=(S-1)/2+1-k;
    while(l=k+1)ans=mid,r=mid-1;//同样是由于算0
            else l=mid+1;
    }
    return S-ans;
}
signed main()
{
    int T;scanf("%lld",&T);
    while(T--)printf("%lldn",solve());
    return 0;
}

后记：这个题折磨了我半个下午加半个晚上，不过也算是迄今为止做过的最难的题之一了，还是很有收获的。以及我真的很想吐槽一下，我函数里重复定义了 (d) 调了快1个小时