1 条题解

  • 0
    @ 2025-11-27 10:48:09
    • 我们学过用数论分块求 商的和\color{orange}{\bf 商的和},而本题求的是 余数的和\color{orange}{\bf 余数的和}
    • 不妨先 把余数用商表示出来\color{orange}{\bf 把余数用商表示出来}
    $$k \bmod i = k - \lfloor\frac{k}{i}\rfloor \times i$$
    • 那么我们要求的是
    $$\begin{aligned} &\sum_{i = 1}^n k \bmod i \\=&\sum_{i = 1}^{n} k - \lfloor\frac{k}{i}\rfloor \times i \\=&n \times k - \sum_{i=1}^{n} \lfloor\frac{k}{i}\rfloor \times i \end{aligned}$$
    #include <bits/stdc++.h>
    using namespace std;
    
    // 数论分块
    // OI Wiki: https://oiwiki.org/math/number-theory/sqrt-decomposition/
    using i64 = long long;
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(0); cout.tie(0);
    
        i64 n, k;
        cin >> n >> k;
    
        // k % i = k - k / i * i
        i64 ans = n * k;
        for (i64 l = 1, r; l <= n; l = r + 1) {
            if (k / l == 0) break;
    
            // k / l == 0 的时候, k / (k / l) 会 除 0
            r = min(k / (k / l), n);
            ans -= (k / l) * (l + r) * (r - l + 1) / 2;
        }
        cout << ans << '\n';
    
        return 0;
    }
    
    • 1

    信息

    ID
    138
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    31
    已通过
    15
    上传者