题解 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代码如下

#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;
}