题目地址：洛谷：【P2261】[CQOI2007]余数求和 – 洛谷、BZOJ：Problem 1257. — [CQOI2007]余数之和

题目描述

给出正整数n和k，计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如G(10, 5)=5 mod 1 + 5 mod 2 + 5 mod 3 + 5 mod 4 + 5 mod 5 …… + 5 mod 10=0+1+2+1+0+5+5+5+5+5=29

输入输出格式

输入格式：
两个整数n k

输出格式：
答案

输入输出样例

输入样例#1：

10 5

输出样例#1：

29

说明

30%: n,k <= 1000
60%: n,k <= 10^6
100% n,k <= 10^9

题解

30%暴力。
60%，我们可以计算出k的剩余类中每个取值在答案中出现的次数，这个次数跟n中k的因数的数量有关，而处理出k的因数需要O(\sqrt{n})的时间，因此这个算法的复杂度是O(n + \sqrt{n})。
100%，我们知道 \displaystyle a \bmod b = a - b \lfloor \frac{a}{b} \rfloor ，也就是说答案是在求 \displaystyle \sum_{i=1}^n k \bmod i = \sum_{i=1}^n (k - i \left\lfloor \frac{k}{i} \right\rfloor) = kn - \sum_{i=1}^n i \left\lfloor \frac{k}{i} \right\rfloor 。 \displaystyle \lfloor \frac{k}{i} \rfloor 有O(\sqrt{n})规模的取值，我们枚举每个取值，计算出符合该值的i的区间即可实现O(\sqrt{n})算法。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cctype>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

LL n, k;

int main() {
    n = readint(); k = readint();
    LL ans = n * k, l = 1, r = 1;
    while(l <= n) {
        if(k / l != 0) r = std::min(k / (k / l), n);
        else r = n;
        ans -= (k / l) * (l + r) * (r - l + 1) / 2;
        l = r + 1;
    }
    printf("%lld", ans);
    return 0;
}