Luogu 4900 食堂

一道把很多东西放在一起的练手题。

$$\sum_{i = A}^{B}\sum_{j = 1}^{i}\left \{ \frac{i}{j} \right \} = \sum_{i = A}^{B}\sum_{j = 1}^{i}\frac{n - \left [ \frac{n}{j}\right] * j}{i} = \sum_{i = A}^{B}(i * \sum_{j = 1}^{i}inv(j) - \sum_{j = 1}^{i}\left \lfloor \frac{n}{j} \right \rfloor)$$

这样子把里面的$(i * \sum_{j = 1}^{i}inv(j) - \sum_{j = 1}^{i}\left \lfloor \frac{n}{j} \right \rfloor)$算出来做个前缀和就好了。

前面的那个东西可以$O(n)$递推然后前缀和算出来，而后面的那个东西其实就是$\sum_{i = 1}^{n}d(i)$（$d(i)$表示$i$的约数个数）。

证明:

$$\sum_{i = 1}^{n}d(i) = \sum_{i = 1}^{n}\sum_{j = 1}^{i}\left [ j| i\right] = \sum_{j = 1}^{n}\sum_{i = 1}^{n}\left [ j| i\right] = \sum_{i = 1}^{n}\left \lfloor \frac{n}{i} \right \rfloor$$

这样子线性筛之后前缀和就做完了。

记得数组开少一点……我就是这样MLE了一次。

时间复杂度$O(n)$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = 1e6 + ;

const int Maxn = 1e6;

const ll P = 998244353LL;

int testCase, pCnt = , pri[N], low[N];

ll inv[N], d[N], h[N];

bool np[N];

template <typename T>

inline void read(T &X) {

    X = ; char ch = ; T op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

template <typename T>

inline void inc(T &x, T y) {

    x += y;

    if(x >= P) x -= P;

}

inline void sieve() {

    d[] = ;

    for(int i = ; i <= Maxn; i++) {

        if(!np[i])

            pri[++pCnt] = i, low[i] = i, d[i] = ;

        for(int j = ; i * pri[j] <= Maxn && j <= pCnt; j++) {

            np[i * pri[j]] = ;

            if(i % pri[j] == ) {

                low[i * pri[j]] = pri[j] * low[i];

                if(low[i] == i) d[i * pri[j]] = d[i] + ;

                else d[i * pri[j]] = d[i / low[i]] * d[pri[j] * low[i]];

                break;

            }

            low[i * pri[j]] = pri[j];

            d[i * pri[j]] = d[i] * d[pri[j]];

        }

    }

    for(int i = ; i <= Maxn; i++) inc(d[i], d[i - ]);

}

int main() {

    sieve();

    inv[] = 1LL;

    for(int i = ; i <= Maxn; i++) inv[i] = inv[P % i] * (P - P / i) % P;

    for(int i = ; i <= Maxn; i++) inc(inv[i], inv[i - ]);

    for(int i = ; i <= Maxn; i++) h[i] = (1LL * i * inv[i] % P - d[i] + P) % P;

    for(int i = ; i <= Maxn; i++) inc(h[i], h[i - ]);

    read(testCase);

    for(int l, r; testCase--; ) {

        read(l), read(r);

        printf("%lld\n", (h[r] - h[l - ] + P) % P);

    }

    return ;

}

巴特西

Luogu 4900 食堂

最新文章

热门文章