問題の定式化

事前に以下の判定を行います。

• \(A=B\) の場合は \(A\)（ひいては \(B\)）の倍数の人数にしか分割できません。よって \(L=R=kA\) を満たすときに限り答えは \(k\)、それ以外は \(-1\) です。以降は
• \(g=\gcd(A,B)\neq 1\) の場合、参加人数は \(g\) の倍数でなければ構成できません。\(L\neq R\) なら直ちに \(-1\)、\(L=R\) かつ \(g\mid L\) なら atcoder::crt などで \(sA+tB=L\) を解きます（\(g\nmid L\) なら答えは \(-1\)）。

以降は\(A < B\) を仮定します。 参加人数 \(x\) に対して最小のチーム数を達成する解では、\(A\) 人チームは高々 \(B-1\) 個になります。もし \(A\) 人チームが \(B\) 個以上存在するなら、\(B\) 個の \(A\) 人チームをまとめて \(A\) 個の \(B\) 人チームに置き換えることで、同じ参加人数でチーム数を減らせるからです。 逆に、\(A\) 人チームが \(B\) 個未満である解が存在するなら、その解がその参加人数における最小チーム数です。 したがって、解が \(-1\) ではない場合、次の整数計画問題を解けば十分です。

\[ \begin{aligned} \mathrm{maximize}&\quad s+t\\ \mathrm{s.t.}&\quad sA+tB=x\\ &\quad s,t \in \mathbb{Z}_{\geq 0}\\ &\quad 0 \leq s < B \end{aligned} \]

解法

\(g=\gcd(A, B)=1\) の場合

各参加人数 \(x\) について \(sA\equiv x \pmod B\) を満たす \(s\) は一意に定まります。\(A\) の逆元を \(A^{-1}\)（\(\bmod B\)）と書くと、\(s \equiv xA^{-1} \pmod B\) です。最適解の一つを \((s^*, t^*)\) とすると、実は \((s^*, t^*)\) を辞書順最大、すなわち

\[ s^* = \max_{L\leq x \leq R} \bigl(xA^{-1} \bmod B\bigr) \]

としてよく（証明後述）、これは min of mod of linear と呼ばれる問題の変種です（参考： [Library Checker] Min of Mod of Linear - maspyのHP））。ここで \(xA^{-1} \bmod B\) は \(0 \leq s < B\) の範囲に正規化した剰余を表します。

\(s^*\) が求まったら、その上で

\[ t^* = \lfloor\frac{R-As^*}{B}\rfloor \]

と計算します。\(As^*\leq L+B-1\) であれば、任意の実行可能解について、 \(As\leq L+B-1\) を満たします。 \(L+B-1\) 以下の整数は \(\mod B \) が等しい \(L\) 以上の整数より大きくなることはないので、\(As\leq x\) となります。

よって、\((s^*, t^*)\) が最適解で、答えは \(s^*+t^*\) です。 \(As^*>L+B-1\) の場合、参加人数が\(As^*-B\) 人の時にチーム分けが出来ないため、 \(-1\) を返します。

\((s^*, t^*)\) を辞書順最大として良いことの証明

\((s^*, t^*)\) が最適解の中で辞書順最大だと仮定したうえで、これが実行可能解の中では辞書順最大ではないと仮定します。このとき、実行可能解の中では辞書順最大ではないことから、

\[\begin{aligned} &\quad L \leq As'+Bt' \leq R\\ &\quad 0 \leq s^* < s' < B\\ &\quad s',t' \in \mathbb{Z}_{\geq 0}\\ \end{aligned}\]

を満たす実行可能解 \((s', t')\) が存在します。 また、\((s^*, t^*)\) は最適解の中では辞書順最大であることから、この解は常に \(s'+t' < s^*+t^*\) を満たします。 ここで、 \(A<B\) より、

\[ As'+Bt' < As'+B(s^*+t^*-s') < As^* + Bt^* \]

が成り立ちます。\((s',t')\) と \((s^*,t^*)\) がともに実行可能解であるため、\((s', s^*+t^*-s')\) も実行可能解であり、これは \((s^*,t^*)\) より辞書順で大きい最適解となります。これは \((s^*, t^*)\) が辞書順最大であるという仮定と矛盾します。