本篇題解大部分內容來自這篇文章
首先題意翻譯:
給定一個正整數 \(S\) ，稱一個正整數集合 \(A\) 是好的，當且僅當它滿足以下條件：
\(A\) 中元素在 \((0,S)\) 之間
不能用 \(A\) 中元素多次相加得到 \(S\)
考慮所有好的集合中元素數量最大且字典序最小的集合 \(A\) ，多次詢問，求集合 \(A\) 從小到大排序後的第 \(k\) 項，或集合大小小於 \(k\)
$ T \le 1000 , S \le 10^{18} $
解法
這什麼神仙題啊光是理解題解就好睏難啊
先考慮性質2：
首先容易發現 \(i,S-i\) 只能在集合中存在一個，若 \(S\) 為偶數則 \(\frac{S}{2}\) 也不能存在於集合中，所以集合的大小小於等於\(\left\lfloor\dfrac{S-1}{2}\right\rfloor\)。
其次，把所有大於 \(\left\lfloor\dfrac{S}{2}\right\rfloor\) 的整數取進集合必然滿足條件，所以最大集合的大小一定為\(\left\lfloor\dfrac{S-1}{2}\right\rfloor\)。
且若要滿足集合大小最大，對於 \(i< \dfrac{S}{2}\)，\(n-i\) 和 \(i\) 一定有一個在集合中。
我們設所有集合 \(A\) 中 \(< \dfrac{S}{2}\)的元素構成集合 \(B\)，顯然 \(B\) 是 \(A\) 的子集，且確定 \(B\) 即可確定 \(A\)。
則 \(B\) 有以下性質：
原因是如果 \(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\) 個。
接下來就來到了同餘最短路的相關部分，考慮對於每個 \(i\in{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\) 了，若一個數 \(t\in B\)，當且僅當 \(t < \frac{S}{2}\) 且 \(t\ge 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 <bits/stdc++.h>
#define N 50
#define M 2000010
#define pii pair<int,int>
#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<d;i++)
if(nw>=f[i])tmp+=(nw-f[i])/d+1;
return tmp;
}
queue<int>q;
void spfa(int nw){
for(int i=0;i<d;i++)q.push(i),in[i]=1;
while(!q.empty()){
int u=q.front(),v=(u+nw)%d;q.pop();in[u]=0;
if(f[v]>f[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<d;i++)f[i]=1e18;
while(1){
int v=1e18;
for(int x=1;x<d;x++){//列舉x，容易發現x肯定不是0
int dn=0;
for(int k=1;k<d;k++){//列舉k，容易發現k取0肯定也不優
int lst=(S-x*k+d*d)%d;//加上d*d用於防負數
dn=max(dn,(S-f[lst])/k+1);
}
if((dn+d-x)%d)dn+=d-(dn+d-x)%d;//確保算出來的下界mod d = x
if(dn<f[x]&&dn<v)v=dn;
}
if(v>=S/2)break;
spfa(v);//更新f
}
int l=1,r=S/2,ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)>=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<=r){
int mid=(l+r)/2;
if(mid-check(mid)+2>=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("%lld\n",solve());
return 0;
}
後記：這個題折磨了我半個下午加半個晚上，不過也算是迄今為止做過的最難的題之一了，還是很有收穫的。以及我真的很想吐槽一下，我函數裡重複定義了 \(d\) 調了快1個小時