\(\displaystyle a=\frac AM,\ b=\frac BM\) とすると、 \((M,A,B)\) が良い組となる条件は \(k=0,1,\ldots,N-1\) に対し \(\lfloor ak+b\rfloor = X_k\) と言い換えられます。 \(\lfloor ak+b\rfloor = X_k\) は \(X_k - ak \le b < X_k+1-ak\) と同値なので、 \(\displaystyle y_{\text{min}}(a) = \max_k \lbrace -ak+X_k\rbrace,\ y_{\text{max}}(a) = \min_k \lbrace -ak+X_k+1\rbrace\) とすると条件は \(y_{\text{min}}(a) \le b < y_{\text{max}}(a)\) となります。

\(y_{\text{min}}(a)\) と \(y_{\text{max}}(a)\) はどちらも高々 \(N\) 本の折れ線で表すことができます。この表し方は CHT を用いることで求められます。

まず \(M\) の値を求めることを考えます。そのために \(M_0\) を固定した際に \(M< M_0\) を満たす良い組がいくつ存在するか？という判定問題を考えます。

\(y_{\text{min}}(a) < y_{\text{max}}(a)\) を満たす区間は各区間で \(y_{\text{min}}(a)\) と \(y_{\text{max}}(a)\) が両方線分となるような高々 \(4\) 個の区間に分割できます。各区間を \((a_l,a_r]\) と表し、その区間での \(y_{\text{min}}(a) \) と \(y_{\text{max}}(a) \) をそれぞれ \(-k_1a+X_1, -k_2a+X_2\) と表すと、 \(A\) に対する条件は \(\lfloor a_lM\rfloor \le A < \lfloor a_rM\rfloor\) となり、 \(A\) を固定した際の \(B\) の個数は \(\displaystyle M(X_2-X_1)-(k_2-k_1)A\) となります。したがって、 \(M < M_0\) を満たす良い組の個数は

\[\sum_{M=0}^{M_0-1}\sum_{A=\lfloor a_lM\rfloor}^{\lfloor a_rM\rfloor-1} \left(M(X_2-X_1)-(k_2-k_1)A\right)\]

となり、この値は floor sum で求まります。

これにより辞書順で \(K\) 番目に小さい良い組の \(M\) の値が求まった後は、同じ式から \(A,B\) の値も復元することができます。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N+\log \max X)\) です。