[BZOJ 1257] [CQOI2007] 余数之和sum 【数学】

题目链接：BZOJ - 1257

题目分析

首先， a % b = a - (a/b) * b，那么答案就是 sigma(k % i) = n * k - sigma(k / i) * i     (1 <= i <= n)

前面的 n * k 很容易算，那么后面的 sigma(k / i) * i，怎么办呢？

我们可以分情况讨论，就有一个 O(sqrtk) 的做法。

1）当 i < sqrtk 时，直接枚举算这一部分。

2）当 i >= sqrtk 时， k / i <= sqrtk 。所以我们就可以枚举 k / i ，即枚举 [1, sqrtk] 的每一个数字。

　  那么，对于我们枚举的每一个数字 x ，以它为 k / i 的 i 一定是连续的一段，它们的和可以用等差数列求和公式算出。

于是就很明确了。

代码

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <iostream>

using namespace std;

int n, k, SQRTK, L, R;

typedef long long LL;

LL Ans;

int main()

{

    scanf("%d%d", &n, &k);

    Ans = 0ll;

    if (n > k) Ans += (LL)(n - k) * k;

    n = n > k ? k : n;

    SQRTK = sqrt(k * 1.0);

    for (int i = 1; i <= SQRTK; i++) {

        if (i > n) break;

        Ans += (LL)k % i;

    }

    for (int i = 1; i <= SQRTK; i++) {

        L = (k / (i + 1)) + 1; L = L <= SQRTK ? SQRTK + 1: L;

        R = k / i; R = R > n ? n : R;

        if (R < L) continue;

        Ans += (LL)(R - L + 1) * ((k % L) + (k % R)) >> 1;

    }

    printf("%lld\n", Ans);

    return 0;

}