「题解」洛谷 P2424 约数和

题目

P2424 约数和

简化题意

(f(x) = sumlimits_{dmid x} d)，求(f(x) + f(x + 1) + dots + f(y)) 的值

思路。

整除分块。

一个数 (i) 在 (1 sim n) 中它的倍数一共有 (leftlfloor dfrac{n}{i} ight floor) 个，即 (i) 对答案的贡献为 (leftlfloor dfrac{n}{i} ight floor imes i)。

设 (g(n)) 表示 (sumlimits_{i = 1}^{n} f(i))，原式可以用下面的方式表示，

[egin{aligned} g(y) - g(x - 1) &= sum_{i = 1}^{y}f(i) - sum_{j = 1}^{x - 1}f(j)\ &= sum_{i = 1} ^ {y} sumlimits_{cmid i} c - sum_{j = 1}^{j - 1} sumlimits_{dmid j} d end{aligned} ]

考虑先枚举约数。

[egin{aligned} &sum_{i = 1} ^ {y} sumlimits_{cmid i} c - sum_{j = 1}^{x - 1} sumlimits_{dmid j} d \ &= sum_{i = 1}^{y} leftlfloor dfrac{y}{i} ight floor imes i - sum_{j = 1}^{x - 1} leftlfloor dfrac{x - 1}{j} ight floor imes j end{aligned} ]

可以用整除分块 (O(2sqrt 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;
}