Description

给出正整数 \(n\) 和 \(k\), 计算 \(f(n, k) = k \bmod 1 + k \bmod 2 + k \bmod 3 + ... + k \bmod n\) 的值, 其中 \(k \bmod i\) 表示 \(k\) 除以 \(i\) 的余数. 例如 \(f(5, 3) = 3 \bmod 1 + 3 \bmod 2 + 3 \bmod 3 + 3 \bmod 4 + 3 \bmod 5 = 0 + 1 + 0 + 3 + 3 = 7\)

Input

输入仅一行, 包含两个整数 \(n, k\).

Output

输出仅一行, 即 \(f(n, k)\).

Sample Input

5 3

Sample Output

7

Data Range

50% 的数据满足:\(1 \leq n, k \leq 1000\)

100% 的数据满足:\(1 \leq n , k \leq 10^9\)

Solution

采用 @hzwer 的一个题解来启发思考 (原来是一道玄学题)

用了一个看起来比较奇怪的方法

首先 x% i=x – (int) (x / i) * i, 这个很好 YY 吧

然后可以找出每个 (int) (x / i) 相等的一段用等差数列求和来做.

可以证明最多分成 sqrt (n) 段

首先我们有这样一个性质:

\[x \bmod i = x - \lfloor \frac{x}{i} \rfloor \times i\]

那么在 \(\lfloor \frac{x}{i} \rfloor\) 相同的时候, 就应当有这样一个特性:

\[\sum_{i=l}^{r} k \bmod i = \sum_{i=l}^{r} k - \lfloor \frac{k}{i} \rfloor \times i\]

\[= (r - l + 1) \cdot k - \lfloor \frac{k}{l} \rfloor \cdot \sum_{i=l}^{r} i\]

\[= (r - l + 1) \cdot k - \lfloor \frac{k}{l} \rfloor \cdot \frac{(r - l + 1) \cdot (l + r)}{2}\]

\[= (r - l + 1) \cdot (k - \lfloor \frac{k}{l} \rfloor \cdot \frac{l + r}{2})\]

然后由于这样的区间最多只有 \(\sqrt{k}\) 个, 所以最后的时间复杂度是 \(O(\sqrt{k})\)

如果有 \(n \geq k\) 那么简单特判把多出来的 \(n - k\) 个 \(k\) 加上就可以了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;

int n, k;
lli res;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &k);
    // Exceeded limit, those are not in determination limit
    if (n > k) {
        res += (lli)(n - k) * k;
        n = k;
    }
    // A group of numbers, in O(sqrt(n))
    int r = 0;
    for (int i = 1; i <= n; i = r + 1) {
        int groups = k / i;
        r = k / groups;
        // Set limits, if encounters exceeding
        if (r >= n)
            r = n;
        res += (lli)(r - i + 1) * k
            - (lli)(r - i + 1) * (i + r) / 2
            * groups;
    }
    printf("%lld\n", res);
    return 0;
}