题目
简化题意
\(f(x) = \sum\limits_{d\mid x} d\)，求\(f(x) + f(x + 1) + \dots + f(y)\) 的值
思路。
整除分块。
一个数 \(i\) 在 \(1 \sim n\) 中它的倍数一共有 \(\left\lfloor \dfrac{n}{i} \right\rfloor\) 个，即 \(i\) 对答案的贡献为 \(\left\lfloor \dfrac{n}{i} \right\rfloor \times i\)。
设 \(g(n)\) 表示 \(\sum\limits_{i = 1}^{n} f(i)\)，原式可以用下面的方式表示，
\[\begin{aligned} g(y) - g(x - 1) &= \sum_{i = 1}^{y}f(i) - \sum_{j = 1}^{x - 1}f(j)\\ &= \sum_{i = 1} ^ {y} \sum\limits_{c\mid i} c - \sum_{j = 1}^{j - 1} \sum\limits_{d\mid j} d \end{aligned} \]
考虑先枚举约数。
\[\begin{aligned} &\sum_{i = 1} ^ {y} \sum\limits_{c\mid i} c - \sum_{j = 1}^{x - 1} \sum\limits_{d\mid j} d \\ &= \sum_{i = 1}^{y} \left\lfloor \dfrac{y}{i} \right\rfloor \times i - \sum_{j = 1}^{x - 1} \left\lfloor \dfrac{x - 1}{j} \right\rfloor \times j \end{aligned} \]
可以用整除分块 \(O(2\sqrt n)\) 求出答案。
Code
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
long long solve(int x) {
long long ans = 0;
for (int i = 1, j = 0; i <= x; i = j + 1) {
j = x / (x / i);
ans += 1ll * (x / i) * (1ll * (j - i + 1) * (1ll * j + i) / 2);
}
return ans;
}
int main() {
int x, y;
std::cin >> x >> y;
std::cout << solve(y) - solve(x - 1);
return 0;
}