基本思路

题目要求计算:

$$f(x) + f(x + 1) + f(x + 2) ... f(y - 1) + f(y)$$

再加上求单个函数并不好算，反而对于此函数来说，求前缀和会更为方便。

设：

$$S(n) = \sum f(n)$$

那么:

数字$1$会对答案贡献$\frac{x}{1}$次，即：$\lfloor \frac{x}{1} \rfloor \times 1$

数字$2$会对答案贡献$\frac{x}{2}$次，即：$\lfloor \frac{x}{2} \rfloor \times 2$

数字$3$会对答案贡献$\frac{x}{3}$次，即：$\lfloor \frac{x}{3} \rfloor \times 3$

所以:

$$S(n) = \sum(\lfloor \frac{n}{i} \rfloor \times i)$$

可以$O(n)$求出$S(n)$

代码I

signed main()
{
    int x = read() - 1, y = read();
    if(x < 0) x = 0;
    int ans1 = 0, ans2 = 0;
    for(_R int i = 1;i <= y;i++)
        ans1 += (y / i) * i;
    for(_R int i = 1;i <= x;i++)
        ans2 += (x / i) * i;
    printf("%lld", ans1 - ans2);
    return 0;
}

不能拿到满分。

优化

观察这个式子：

$$(x / i) * i$$

注意到$\lfloor \frac{x}{i} \rfloor$随着$i$的增长并不是一直在变化的，而是分段的。

形式化的讲，

$$g(i) = \lfloor \frac{x}{i} \rfloor$$

这个函数是单调呈现阶梯状递增的。

只要求出这个阶梯状函数的拐角，两拐角之间的平台可以设为常熟$k$。

那么在某段区间内，算式能变成

$$k \times i$$

利用等差数列求和即可。

现在的关键在于找到$\lfloor \frac{x}{i} \rfloor$发生改变的拐点。

由于我太菜了，我不能直接算出来，但是比较好想的就是，因为函数$g(i)$是单调的，所以可以二分拐点。

代码II

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define _R register
#define int long long 
using namespace std;
int x, y;
long long SolveSegment(const int L,const int R,const int Val)
{
    return (((L + R) * 1LL * (R - L + 1LL)) / 2LL) * 1LL * Val;
}
long long GetIt(int x)
{
    if(x <= 0) return 0LL;
    if(x == 1) return 1LL;
    long long res = 0;
    for(_R int i = 1;i < x;){
        int now = x / i;
        int L = i;
        int R = x;
        int ans;
        if(now == 1){
            res += SolveSegment(ans, x, 1);
            break;
        }
        while(L < R)
        {
            int mid = (L + R) >> 1;
            if((x / mid) < now) ans = mid, R = mid;
            else L = mid + 1;
        }
        res += SolveSegment(i, ans - 1, x / i);
        i = ans;
    }
    return res;
}
signed main()
{
    cin >> x >> y;
    long long ans =  GetIt(y) - GetIt(x - 1);
    printf("%lld",ans);
    return 0;
}

本文目的在于提供一种笔者感觉比较好想的思路，但是感觉既然做到这道题了，就尽量去看看更高级的做法？

By Shu_Yu_Mo