顺着专项训练做题，第一次写 AGC 题解，求过 qwq。
题意
定义一个定义在整数域上的二元函数 \(f(A,B)\)，值域为由 A 和 B 组成的字符串集合，具体定义如下：
- \(|f(A,B)|=A+B\)。
- \(f(A,B)\) 恰好包含 \(A\) 个
A和 \(B\) 个B。 - \(f(a,b)\) 最长字符相同的连续子串的长度最小。
- \(f(a,b)\) 在满足条件的串中字典序最小。
求 \(f(a_i,b_i)\) 从第 \(c_i\) 个字符到第 \(d_i\) 个字符所组成的子串。
做法
首先注意到最长字符相同的连续子串长度最小为
\[l=\max(\lceil\frac a{b+1} \rceil,\lceil \frac b{a+1} \rceil)=\frac{\max(a,b)}{\min(a,b)+1}
\]
则不难发现，要使字典序最小，则字符串大概长这样：
\[|A\dots ABA\dots AB\dots|B\dots BAB\dots BA\dots|
\]
分成了两段。
设前半部分被 A 分成的连续段数为 \(x\)（段与段之间用一个 B 隔开），则前半部分至少包含 \(l(x-1)+1\) 个 A 和 \(x-1\) 个 B，则剩余的后半部分中有 \(A-l(x-1)-1\) 个 A 和 B-x+1 个 B，从而有不等式
\[B-x+1 \le l(A-l(x-1)-1+1)
\]
解得
\[x \le \frac{l^2+lA-B-1}{l^2-1}
\]
为了是字典序更小，我们应取理论 \(x\) 的最大值，注意到不等式右边是分式，从而我们应当分类分母是否为 \(0\) 的情况：
- 若 \(l^2-1=0\)，即 \(l=1\)（负根舍去），从而前半部分全部为
A，于是 \(x=A\)。 - 若 \(l^2-1\ne 0\)，即 \(l\ne 1\)，则：
\[x_{\max}=\max(1,\lfloor \frac{l^2+lA-B-1}{l^2-1} \rfloor)
\]
接下来考虑分界点的问题。
由于后半部分 B 的个数为 \(B-x+1\) 需要用 A 进行分隔，因此 A 的个数为 \(\lfloor (B-x+1)/l\rfloor\)，从而后半部分总长为
\[(B-x+1)+\lfloor \frac{B-x+1}l \rfloor
\]
从而前半部分长，即分界点为
\[(A+B)-(B-x+1)-\lfloor \frac{B-x+1}l \rfloor=A+x-1-\lfloor \frac{B-x+1}l \rfloor
\]
综合上面，就做完了。
Submission。