CF616E Sum of Remainders

发布于 14 天前  13 次阅读


link

Sol

现在让你求的是

\sum_{i = 1}^{m} n \ mod \ i

模运算这种东西就是带余除法,然后你发现余数你也很不好算。就考虑把模运算改成带余除法的形式

我们知道: x \div i = \lfloor \frac{x}{i} \rfloor + x - (i \times \lfloor \frac{x}{i} \rfloor)

所以现在要求的东西就是

\sum_{i=1}^{m} n - (i \times \lfloor \frac{n}{i} \rfloor)

n \times m - \sum_{i=1}^{m} i \times \lfloor \frac{n}{i} \rfloor

所以后面的东西整除分块一下就好了

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mod = 1e9 + 7;

int n, m;

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

inline int qPow(int a, int b)
{
    int ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        b >>= 1, a = a * a % mod;
    }
    return ans % mod;
}

inline int minux(int a, int b) { return (a - b + 10 * mod) % mod; }

signed main()
{
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    n = read(), m = read();
    int ans = (n % mod) * (m % mod) % mod, mul = qPow(2, mod - 2);
    for (int l = 1, r = 0; l <= m; l = r + 1) {
        if (n / l == 0) r = m;
        else r = std::min(m, (n / (n / l)));
        ans = (ans - 1ll * (n / l) % mod * ((l + r) % mod) % mod * ((r - l + 1ll) % mod) % mod * mul % mod + 10ll * mod) % mod;
    }
    printf("%lld\n", ans % mod);
    return 0;
}

朴实沉毅