计蒜客 41302 - K Sum

题目链接：ICPC 2019 南京网络赛 E 题

思路

\(f_n(k)\)化简得： \[ f_n(k) \begin{aligned} & = \sum_{u=1}^{n} \lfloor \frac{n}{u} \rfloor ^ k  \sum_{d|u} d^2 \mu(\frac{u}{d}) \end{aligned} \] 代入目标式并交换求和次序： \[\begin{aligned} & \sum_{i=2}^{k} \sum_{u=1}^{n} \lfloor \frac{n}{u} \rfloor ^ k  \sum_{d|u} d^2 \mu(\frac{u}{d}) \\ =& \sum_{u=1}^{n}\sum_{i=2}^{k} \lfloor \frac{n}{u} \rfloor ^ k  \sum_{d|u} d^2 \mu(\frac{u}{d}) \\ =& \sum_{u=1}^{n} t(\lfloor \frac{n}{u} \rfloor)  ({\rm Id}^2 * \mu)(u) \end{aligned} \] 其中\(t(\lfloor \frac{n}{u} \rfloor)\)表示一个等比数列求和的结果，对于比较大的 \(k\)，可以考虑欧拉函数降幂，然后可以整除分块求解。坑点是要特判公比为 \(1\) 的情况，公比为 \(1\) 的时候的 \(k\) 的计算值是 \(k \bmod P\) 而不是 \(k \bmod \varphi(P)\)。 下面考虑求式中 Direchlet 卷积的前缀和。\(n\)的范围是\(10^9\)，考虑使用亚线性筛。

记 \(f(x) =({\rm Id}^2 * \mu)(x)\)，\(g(x) = 1\)，则\(f * g = {\rm Id}^2 * \mu * 1 = {\rm Id}^2 * \epsilon = {\rm Id}^2\)，可求前缀和，考虑杜教筛。 设\(F(n) = \sum_{x=1}^{n} f(x)\)，则可以对\(f*g\)求和推得: \[ F(n) = \frac{n(n+1)(2n+1)}{6} - \sum_{d=2}^{n} F(\lfloor \frac{n}{d} \rfloor) \] 线性筛预处理\(n \leq 10^6\)，然后杜教筛即可。

渐进时间复杂度\(O(T (n^{\frac{2}{3}} + \sqrt{n} \times \log P) )\)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAX_LEN = 1000000 + 5;
const LL P = LL(1E9) + 7;
const LL PHI_P = LL(1E9) + 6;
const LL INV_6 = 166666668;
inline LL getPow(LL u, LL v) {
    LL ret = 1;
    while (v) {
        if (v & 1) ret = ret * u % P;
        u = u * u % P;
        v >>= 1;
    }
    return ret;
}
inline LL add(LL u, LL v, LL x = 0, LL y = 0) { return (((u + v) % P) + ((x + y) % P) % P); }
inline LL sub(LL u, LL v) { return (((u - v) % P) + P) % P; }
inline LL mul(LL u, LL v, LL x = 1, LL y = 1) { return (((u * v) % P) * ((x * y) % P) % P); }
bool vis[MAX_LEN];
LL p[MAX_LEN], low[MAX_LEN], tot;
LL f[MAX_LEN];
void linearSieve() {
    vis[0] = vis[1] = 1;
    low[1] = f[1] = 1;
    for (LL i = 2; i < MAX_LEN; ++i) {
        if (!vis[i]) {
            p[++tot] = i;
            f[i] = sub(i * i % P, 1);
            low[i] = i;
        }
        for (LL j = 1; j <= tot && i * p[j] < MAX_LEN; ++j) {
            vis[i * p[j]] = 1;
            if (i % p[j] == 0) {
                low[i * p[j]] = low[i] * p[j];
                if (low[i] == i) f[i * p[j]] = mul(p[j], p[j]) * f[i] % P;
                else f[i * p[j]] = f[i / low[i]] * f[p[j] * low[i]] % P;
                break;
            } else {
                f[i * p[j]] = f[i] * f[p[j]] % P;
                low[i * p[j]] = p[j];
            }
        }
    }
    for (LL i = 1; i < MAX_LEN; ++i) f[i] = (f[i] + f[i - 1]) % P;
}
unordered_map <LL, LL> hashS;
LL F(LL x) {
    if (x < MAX_LEN) return f[x];
    if (hashS.find(x) != hashS.end()) return hashS[x];
    LL ret = mul(x, x + 1, x * 2 + 1, INV_6);
    LL l, r;
    for (l = 2; l <= x; l = r + 1) {
        r = x / (x / l);
        ret = sub(ret, F(x / l) * (r - l + 1) % P);
        ret = ((ret % P) + P) % P;
    }
    return hashS[x] = ret;
}
const LL MAX_N = 100000 + 5;
LL T, N, K, SP;
char str[MAX_N];
int main() {
    linearSieve();
    // for (int i = 1; i <= 10; ++i) printf("f[%d] = %lld\n", i, f[i] - f[i - 1]);
    scanf("%lld", &T);
    for (LL cs = 1; cs <= T; ++cs) {
        hashS.clear();
        scanf("%lld", &N);
        // memset(str, '\0', sizeof str);
        scanf("%s", str);
        // printf("N = %lld, K = %s\n", N, str);
        LL len = strlen(str);
        K = 0; SP = 0;
        for (LL i = 0; i < len; ++i) {
            K = (K * 10 + (str[i] - '0')) % PHI_P;
            SP = (SP * 10 + (str[i] - '0')) % P;
        }
        K = ((K - 1) % PHI_P + PHI_P) % PHI_P;
        SP = ((SP - 1) % P + P) % P;
        LL l, r, ans = 0;
        for (l = 1; l <= N; l = r + 1) {
            r = N / (N / l);
            LL b = N / l;
            LL invDown = getPow(sub(1, b), P - 2);
            LL right = sub(1, getPow(b, K));
            LL con = mul(b, b, invDown, right);
            if (b == 1) con = SP;
            ans = add(ans, mul(con, sub(F(r), F(l - 1))));
        }
        printf("%lld\n", ans);
    }
    return 0;
}