「Hdu 5608」function (莫比乌斯反演 + 杜教筛)

hdu 5608
题意：给定$n$和函数$f, g$满足
$$
g(n)=n^2−3n+2\\
g(n)=\sum_{d|n} f(d)
$$
求
$$
\sum_{i=1}^n f(i) \mod 10^9+7
$$

显然$f * I = g$，杜教筛即可。
即
$$
S(n)=\sum_{i=1}^n g(i) - \sum_{i=2}^n S(\lfloor \frac nd \rfloor)
$$
将$g$每个项分离出来，用平方数列前缀和公式+等差数列公式即可求解。

对于前$n^{\frac 23}$的$f$，反演一下即可。即
$$
f(n)=\sum_{d|n} g(d) \mu(\frac nd)
$$
注意这个式子不是很常用。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

int T;

namespace flyinthesky {

    const int N = 1000000;
    const LL MO = 1000000000 + 7;

    LL n, f[N + 5], inv3; 
    int mu[N + 5], pri[400000 + 5], vis[N + 5], tot;

    map<LL, LL > ansf;

    LL ksm(LL a, LL b) {
        LL ans = 1ll, bs = a;
        while (b) {
            if (b & 1) ans = (ans * bs) % MO;
            bs = (bs * bs) % MO;
            b >>= 1;
        }
        return ans;
    }

    LL getf(LL n) {
        if (n <= N) return f[n];
        if (ansf[n]) return ansf[n];
        LL ret = (n * n % MO * n % MO + 2ll * n % MO - 3ll * n % MO * n % MO) * inv3 % MO;
        ret = (ret % MO + MO) % MO;
        int l = 2;
        while (l <= n) {
            int r = n / (n / l);
            ret = ((ret - (r - l + 1ll) * getf(n / l) % MO) % MO + MO) % MO;
            l = r + 1;
        }
        return ansf[n] = ret;
    }

    void init() {
        ms(f, 0), ms(mu, 0), ms(pri, 0), ms(vis, 0), tot = 0;
        mu[1] = 1;
        for (int i = 2; i <= N; ++i) {
            if (!vis[i]) pri[++tot] = i, mu[i] = -1;
            for (int j = 1; j <= tot && 1ll * pri[j] * i <= 1ll * N; ++j) {
                vis[pri[j] * i] = 1;
                if (i % pri[j] == 0) {
                    mu[pri[j] * i] = 0;
                    break ;
                } else mu[pri[j] * i] = mu[pri[j]] * mu[i];
            }
        }
        for (int i = 1; i <= N; ++i)
        for (int j = i; j <= N; j += i) f[j] = (f[j] + (i - 2ll) * (i - 1ll) % MO * mu[j / i] % MO + MO) % MO;
        for (int i = 1; i <= N; ++i) f[i] = (f[i] + f[i - 1]) % MO;
        inv3 = ksm(3, MO - 2);
    }
    void clean() {
    }
    int solve() {

        clean();
        scanf("%lld", &n);
        printf("%lld\n", getf(n));

        return 0;
    }
}
int main() {
    scanf("%d", &T);
    flyinthesky::init();
    while (T--) flyinthesky::solve();
    return 0;
}
/*
1
2000001
*/