XDU2023寒假训练1.16

这场纯被队友带飞。

B. Linear Congruential Generator

$$\sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}\Big(X_i\bmod (X_j+1)\Big)$$

可以化成

$$\sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}\Big(X_i-\lfloor\dfrac{X_i}{x_j+1}\rfloor(X_j+1)\Big)$$

即

$$(r_2-l_2+1)\sum_{i=l_1}^{r_1} X_i -\sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}\lfloor\dfrac{X_i}{x_j+1}\rfloor(X_j+1)$$

根据取模的特性，是有循环节的。

统计两个区间的数出现的次数来计算上面这个式子。