令 $a=\frac{A}{M},b=\frac{B}{M}$，则 $X_k=\lfloor ak+b\rfloor$，即 $X_k\le ak+b< X_k+1$。固定 $a$ 后转化为 $b$ 的限制即为 $X_k+ak\le b< X_k+1-ak$。

令 $y_{\min}(a)=\max_k\{X_k-ak\}$，$y_\max(a)=\min_k\{X_k+1-ak\}$，则 $a,b$ 需要满足的条件是 $y_\min(a)\le b< y_\max(a)$。

$y_\min(a)$ 和 $y_\max(a)$ 分别可以表示成不超过 $N$ 段的折线，这个折线可以用凸包求出。然后我们可以找出满足 $y_\min(a)< y_\max(a)$ 的区间，这个区间也被分成若干段，每一段中 $y_\min(a)$ 和 $y_\max(a)$ 都是一次函数。事实上我们可以证明这样的段只有 $O(1)$ 段，具体证明可以参考官方题解。

考虑如何计算 $M< M_0$ 的三元组数量，只要能计算该数量就能二分 $M$ 的取值。考虑每一段 $(a_l,a_r]$ 中有 $y_\min(a)=k_1a+l_1,y_\max(a)=k_2a+l_2$，枚举 $M< M_0$，则 $A=Ma\in(Ma_l,Ma_r]$，即 $\lfloor Ma_l\rfloor < A\le \lfloor Ma_r\rfloor$。$y_\min(a)\le b< y_\max(a)$ 等价于 $k_1A+l_1M\le B< k_2A+l_2M$，因此总数可以用下面的式子计算： $$ \sum_{M=0}^{M_0-1}\sum_{A=\lfloor Ma_l\rfloor+1}^{\lfloor Ma_r\rfloor} ((k_2-k_1)A+(l_2-l_1)M) $$ 这个式子可以用类欧几里得算法快速计算。

在得到 $M$ 的取值后，可以用同样的式子求出 $A$ 和 $B$ 的取值。时间复杂度 $O(N+\log ^2V)$，其中 $V=2^{30}$。注意求和的过程中涉及到的数非常大，需要使用高精度或者在模多个模数的意义下计算。