题解 P2424 【约数和】
ShuYuMo
2019-10-23 00:40:25
# 基本思路
题目要求计算:
$$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
```cpp
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
```cpp
#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](https://shuyumo-1258548314.cos-website.ap-beijing.myqcloud.com/mainpage/index.html)