抛出问题

题目来源：洛谷一位大佬的比赛的第一题。

题目大意：求下面式子的值：

$$\sum^{B} _ {i=A}\sum^{i} _ {j=1}\left \lfloor \frac{i}{j} \right \rfloor \times \left ( -1\right )^j$$

题目解答

比赛解答

比赛解答链接

$O(\sqrt{B})$的原创解答在本博客最下面。

各位也可以参考一下另一位大佬写的 $O(\sqrt{B})$的做法：大佬博客链接。

冷静分析

第一时间想到的是内部分块做法，外部线性暴力，不过细细一看，这绝对会超时的啊（你自己都说暴力了）！因此我们需要一个线性做法。

那么我们就需要将式子变形了。

$$
\sum^{B} _ {i=A}\sum^{i} _ {j=1}\left \lfloor \frac{i}{j} \right \rfloor \times \left ( -1 \right )^j
=\sum^{B} _ {i=1}\left ( \left ( -1 \right )^i \sum^{B} _ {j=A} \left \lfloor \frac{j}{i} \right \rfloor \right )
$$

注意到式子中，我们把 $-1$提出来了，为了使式子等价于原来的式子，我们不得不给式子做一个大手术。因为 $-1$提前了，那么它的幂次只能是 $i$，于是我们将 $i$和 $j$的意义替换，变换式子使得其等价于原来的式子。其中注意 $i>j$时，分式向下取整得 $0$，对答案无影响，所以这两个式子是等价的。

看到这里，你可能还是不知道怎么得到线性做法，我们就这样看：

$$
\sum^{B} _ {i=1}\left ( \left ( -1 \right )^i \sum^{B} _ {j=A} \left \lfloor \frac{j}{i} \right \rfloor \right )
=\sum^{B} _ {i=1}\left ( \left ( -1 \right )^i \left ( \sum^{B} _ {j=1} \left \lfloor \frac{j}{i} \right \rfloor – \sum^{A-1} _ {j=1} \left \lfloor \frac{j}{i} \right \rfloor \right ) \right )
$$

现在 $i$是比较稳定的了，因为当 $i$取一个值时，而 $j$是连续递增的，那么向下取整可以得到连续 $i$个的向下取整的相同的值。

举个例子吧，当 $i=3$时，假设 $j$从 $1$逐一递增到无穷，我们会得到：

$$0,0,1,1,1,2,2,2,3,3,3,\cdots $$

那么我们就可以在 $O(1)$的常数时间内算出里面的和式差，最终我们就得到了时间复杂度为 $O(B)$的算法。

当然，由于 $B$有点大，因此我们需要稍微注意一下常数问题。

不过，在写程序的时候，要注意考虑前面的 $0$的个数是 $i-1$个的。但是总体还是有规律可循，具体看我的程序。

程序实现

#include <cstdio>
int main()
{
    int a, b;
    long long ans = 0, r, s, t;
    scanf("%d%d", &a, &b);
    for(register int i = 1; i <= b; i += 1)
    {
        r = a / i - 1;//因为最后一项长度不定，所以我们确定倒数第二项
        s = (a - r * i - i) * (r + 1);//计算最后一项的长度并求和
        r = (r + 1) * r / 2 * i;//前面项的和
        t = s + r;
        //同理可得
        r = (b + 1) / i - 1;
        s = (b + 1 - r * i - i) * (r + 1);
        r = (r + 1) * r / 2 * i;
        if(i & 1)
            ans -=  s + r - t;
        else
            ans += s + r - t;
    }
    printf("%lld", ans);
    return 0;
}

最大耗时点耗时：237ms。

当然，我还发现了一些牛逼解答方式，总耗时 0ms 的程序，有时间我会学习一下 OwO。

极速解法（原创）

冷静分析

我们再将那个和式进行变换：

$$
\sum^{B} _ {i=1}\left ( \left ( -1 \right )^i \left ( \sum^{B} _ {j=1} \left \lfloor \frac{j}{i} \right \rfloor – \sum^{A-1} _ {j=1} \left \lfloor \frac{j}{i} \right \rfloor \right ) \right )
=\sum^{B} _ {i=1}\left ( \left ( -1 \right )^i \sum^{B} _ {j=1} \left \lfloor \frac{j}{i} \right \rfloor \right ) – \sum^{A-1} _ {i=1}\left ( \left ( -1 \right )^i \sum^{A-1} _ {j=1} \left \lfloor \frac{j}{i} \right \rfloor \right )
$$

我们可以对最外层的和式进行分块运算。

我们只需分成 $4$组进行求和即可，也就是将其分为奇偶和左右部分即可（方便快速高斯求和）。

那么分块具体如何实现呢？

我们发现内部都是有秩序的，虽然将外层的 $i$以不同的值写出，同类合并之后我们会发现有点混乱，但是并非无迹可寻！

因为注意到 $\left \lfloor \frac{j}{i} \right \rfloor$在某几种 $i$的值中（连续的、差为 $2$的 $i$值），如果组成的数的个数不变（比如都有 $1$到 $9$），那么除最后一个数（前面的例子的 $9$），其他数的变化都是同规律线性的（根据比赛题解中提到的结论可得），可以用高斯求和公式算出来。

而组成的数个数不变，当且仅当 $\left \lfloor \frac{j}{i} \right \rfloor$中 $j$取最大值时该式得到的值不变。

就比如上面提到的那个 $9$，因为随着 $i$的变化，比 $9$小的值都会越来越多，而 $9$就会被压出去（可以说是溢出吧 2333），毕竟序列长度只有这么长。

而这个值（例如那个 $9$）的变化也是线性的！因为前面是线性递增，那么上述的 $9$的个数就会线性递减。

那么线性的都可以算出来，仅对最大值的变化讨论即可。而最大值的变化恰恰是有分块的属性（这个不难证明，大家思考一下），于是我们通过内部常数时间，外部分块时间即可算出答案。

严格来说，根号外面至少还有 $4$的常数，但是似乎还有可以优化的地步（蒟蒻我太弱了）。但是时间复杂度还是 $O(\sqrt{B})$的，所以很快就能通过。

由于博主太过激动，导致语言逻辑不够清晰，请多多包涵。

程序实现

#include <cstdio>

int a, b;

//对比 O(B) 的代码，其实只是加了一些高斯求和罢了
inline long long getans(int f)
{
    int rr, q, delta;
    long long ans = 0, r, r_, s, t, l;
    for(register int i = (f ? 1 : 2); i <= a; i = q + 2)
    {
        rr = a / i;
        q = a / rr;
        if((q & 1) && !f)//要偶数却是奇数
            q ^= 1;
        else if(!(q & 1) && f)//要奇数却是偶数
            q -= 1;
        delta = (q - i >> 1) + 1;//中间长度
        r = a / i - 1;//因为最后一项长度不定，所以我们确定倒数第二项
        l = a + 1 - r * i - i;
        s = (r + 1) * (l - (delta - 1) * (r + 1)) * delta;
        //分块的最后一项求和
        r_ = r;//记录
        r = (r + 1) * r * i >> 1;//前面项的和
        r = r * delta + ((1 + r_) * r_ >> 1) * ((delta - 1) * delta);
        //增加的值
        t = s + r;
        if(f & 1)
            ans += t;
        else
            ans -= t;
    }
    for(register int i = (f ? 1 : 2); i <= b; i = q + 2)
    {
        rr = b / i;
        q = b / rr;
        if((q & 1) && !f)//要偶数却是奇数
            q ^= 1;
        else if(!(q & 1) && f)//要奇数却是偶数
            q -= 1; 
        delta = (q - i >> 1) + 1;//中间长度
        r = b / i - 1;//因为最后一项长度不定，所以我们确定倒数第二项
        l = b + 1 - r * i - i;
        s = (r + 1) * (l - (delta - 1) * (r + 1)) * delta;
        //分块的最后一项求和
        r_ = r;//记录
        r = (r + 1) * r * i >> 1;//前面项的和
        r = r * delta + ((1 + r_) * r_ >> 1) * ((delta - 1) * delta);
        //增加的值
        t = s + r;
        if(f & 1)
            ans -= t;
        else
            ans += t;
    }
    return ans;
}

int main()
{
    scanf("%d%d", &a, &b);
    a -= 1;
    printf("%lld", getans(1) + getans(0));
    return 0;
}

单点最大耗时：3ms（由于新测评机的缘故，至少都是 2ms 的点，应该可以 0ms 的，没赶上时机哎）。

写在最后

感谢比赛举办者提供的题目和题解。
本题解仅作为个人收藏，不做任何商业用途，禁止任何人做商业用途传播。
另外，如果作者认为不妥，可以告诉我，我会马上删掉。
程序为个人智力成果，仅根据公式写出，未查看标准程序，如需转载，请注明出处。