# 「LOJ 138」类欧几里得算法

$$\sum_{x = 0} ^ {n} x ^ {k_1} {\left \lfloor \frac{ax + b}{c} \right \rfloor} ^ {k_2}$$

LOJ 138

### 题解

$$\lfloor \frac{b} {c} \rfloor ^ {k_2} \sum_{x = 0} ^ n x ^ {k_1}$$，此时就是一个自然数幂和，令 $B$ 表示伯努利数，$S_k(n) = \sum\limits_{x = 0} ^ n x ^ k$，则
$$S_k(n) = \frac {1} {k + 1}\sum_{j = 0} ^ k (-1) ^ j \binom{k + 1} {j} B_j n ^ {k + 1 - j}$$

\begin{aligned}\sum_{x = 0} ^ n x ^ {k_1} \lfloor \frac {ax + b} {c} \rfloor &= \sum_{x = 1} ^ n x ^ {k_1}(qx + \lfloor \frac{rx + b} {c} \rfloor) ^ {k_2} \\ &= \sum_{i = 0} ^ {k_2} \binom {k_2} {i}q ^ i \sum_{x = 0} ^ n x ^ {k_1 + i}\lfloor \frac{rx + b} {c} \rfloor ^ {k_2 - i}\end{aligned}。

$$\lfloor \frac{cy - b - 1} {a} \rfloor \lt x \leq \lfloor \frac{c(y + 1) - b - 1} {a} \rfloor$$

$$\sum_{x = 0} ^ n x ^ {k_1} \lfloor \frac{ax + b} {c} \rfloor ^ {k_2} = S_{k_1}(n)m ^ {k_2} + \sum_{y = 1} ^ m \big( (y - 1) ^ {k_2} - y ^ {k_2} \big)S_{k_1}(\lfloor \frac{cy - b - 1} {a} \rfloor)$$

$$(y - 1) ^ {k_2} - y ^ {k_2} = \sum_{i = 0} ^ {k_2 - 1}\binom{k_2} {i}(-1) ^ {k_2 - i}y ^ i$$

$$\sum_{x = 0} ^ {n}x ^ {k_1}\lfloor \frac {ax + b} {c} \rfloor ^ {k_2} = S_{k_1}(n)m ^ {k_2} + \sum_{i = 0} ^ {k_2 - 1}\sum_{h = 0} ^ {k_1 + 1}\big(\binom{k_2} {i}(-1) ^ {k_2 - i}P_{k_1, h}\sum_{y = 1} ^ m y ^ i\lfloor \frac{cy - b - 1} {c} \rfloor ^ h \big)$$