题解 P4863 【JerryC Loves Driving】

首先一想直接暴力 $A$ 到 $B$ 然后内部分块，然后写出来本地一跑 `A=1 B=2000000` 就T了 于是列表找规律  发现在 $j$ 相同的情况下，$\left\lfloor\dfrac{i}{j}\right\rfloor \times (-1)^j$ 的值仍有规律。 可以发现，对于 $j$ 相同时的 $\left\lfloor\dfrac{i}{j}\right\rfloor \times (-1)^j$ 的每一个值，都连续出现了 $j$ 次 于是将外部循环 $i$ 改为循环 $j$。 求式子 $$ \sum_{i=A}^B\sum_{j=1}^i\left\lfloor\dfrac{i}{j}\right\rfloor\times(-1)^j $$ 即为求表中 $i$ 列由 $A$ 到 $B$ ，$j$ 列由 $1$ 到 $B$ 的矩形数值的和 对于每一列的值，可以使用等差数列求和公式计算 设 $l=\left\lfloor\dfrac{A}{j}\right\rfloor$ 且 $r=\left\lfloor\dfrac{B}{j}\right\rfloor$ 计算 $A$ 至 $B$ 之间的和，可以变为计算 $j$ 个首项为 $0$，末项为 $r$，公差为 $1$ 的等差数列之和减去不属于 $A$ 与 $B$ 之间的部分 等差数列之和为 $\dfrac{r\times(r+1)}{2}\times j$ 先计算 $A$ 之前的和，可发现它由 $j$ 个首项为 $0$，末项为 $l$，公差为 $1$ 的等差数列去掉在 $A$ 里面的 $l$ 组成 在 $A$ 里面的 $l$ 有 $l\times j+j-A$ 个，就是 $l$ 的最大值减去 $A$ 为在内部的 $l$ 的个数 式子为 $\dfrac{l\times(l + 1)}{2}\times j-l \times(l\times j+j-A)$ 对于超出 $B$ 的部分，与 $A$ 相同处理 得到式子 $(r\times j+j - B - 1) \times r$ （ 减去 $1$ 是因为得到 $r$ 的最大值为 $r\times j + j-1$ ） AC代码如下 ``` cpp #include <bits/stdc++.h> using namespace std; int A, B; long long ans; int main() { cin >> A >> B; for (int j = 1; j <= B; j++) { long long sum = 0; long long l = A / j; long long r = B / j; sum = r * (r + 1) * j / 2; long long front = l * (l + 1) / 2 * j - l * ((l + 1) * j - A); long long back = ((r + 1) * j - B - 1) * r; sum = sum - front - back; if (j % 2 == 0) ans += sum; else ans -= sum; } cout << ans << endl; return 0; } ```