Skip to content

洛谷 - P2261 余数求和

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

题面

题目描述

给出正整数 nnkk,请计算:

G(n,k)=i=1nk mod iG(n, k) = \sum_{i = 1}^n k \bmod i

其中 k mod ik \bmod i 表示 kk 除以 ii 的余数。

输入格式

输入只有一行两个整数,分别表示 nnkk

输出格式

输出一行一个整数表示答案。

输入输出样例

样例输入 #1

10 5

样例输出 #1

29

样例解释 #1

G(10,5)=0+1+2+1+0+5+5+5+5+5=29G(10, 5) = 0 + 1 + 2 + 1 + 0 + 5 + 5 + 5 + 5 + 5 = 29

数据范围与约定

  • 对于 30%30\% 的数据,保证 n,k103n, k \leq 10^3
  • 对于 60%60\% 的数据,保证 n,k106n, k \leq 10^6
  • 对于 100%100\% 的数据,保证 1n,k1091 \leq n, k \leq 10^9

思路

i=1nk mod i=i=1nkiki=nki=1ni×ki\begin{aligned} & \sum_{i = 1}^{n} k \bmod i \\ = & \sum_{i = 1}^{n} k - i \lfloor \frac{k}{i} \rfloor \\ = & nk - \sum_{i = 1}^{n} i \times \lfloor \frac{k}{i} \rfloor \\ \end{aligned}

然后使用整除分块计算。设 t=klt = \lfloor \frac{k}{l} \rfloor,若 t0t \ne 0,则 r=ktr = \lfloor \frac{k}{t} \rfloor,否则 r=nr = n。将 ans\it ans 减去 (l+r)/2×t×(rl+1)(l + r) / 2 \times t \times (r - l + 1)(区间内 ii 的平均值 × kl\lfloor \frac{k}{l} \rfloor × 区间长度)。

t=0t = 0 时可知余下部分全为 00,退出循环即可。

代码

#include <iostream>

using std::cin;
using std::cout;
const char endl = '\n';

long long n, k, ans;

int main() {
    std::ios::sync_with_stdio(false);

    cin >> n >> k;

    ans = n * k;

    for (long long l = 1, r; k / l && l <= n; l = r + 1) {
        r = std::min(k / (k / l), n);
        ans -= (r + l) * (k / l) * (r - l + 1) / 2;
    }

    cout << ans << endl;

    return 0;
}