problemId:15693 Day2 T1

日常竞赛测试讨论
,
1

problemId:15693

Day2 T1

题意：

让你求 \mathop{\sum_{i=1}^n} k \mathop{\mathrm{mod}} i(1 \le n \le 10^9)

思路：

暴力：

直接循环 1 \sim n 计算，时间复杂度 $O(n)$，60 分。

正解：

考虑化简一下：
\mathop{\sum_{i=1}^n} k \mathop{\mathrm{mod}} i
=\mathop{\sum_{i=1}^n} k-\lfloor \frac{k}{i} \rfloor \cdot i
=nk-\mathop{\sum_{i=1}^n} \lfloor \frac{k}{i} \rfloor \cdot i

然后就可以愉快的整数分块啦。

\texttt{AC Code}

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll res;
int n, k;

int main() {
    scanf("%d%d", &n, &k);
    for (int l = 1, r = 0; l <= n; l = r + 1) {
        if (l <= k) {
            r = min(k / (k / l), n);
            res += 1ll * (2 * k - (l + r) * (k / l)) * (r - l + 1) / 2;
        } else {
            res += 1ll * (n - l + 1) * k;
            break;
        }
    }
    printf("%lld", res);
    return 0;
}