2019南京网络赛 E. K SUM

题目大意：

f_n(k)=\sum_{l_1=1}^n \sum_{l_2=1}^n … \sum_{l_k=1}^n \left(\gcd\left(l_1,l_2,…,l_k\right)\right)^2

1 \le n \le 10^9,2 \le k \le {10}^{10^5}，计算\sum_{i=2}^k {f_n(i)}

问题分析：

\begin{aligned}
f_n(k)&=\sum_{l_1=1}^n \sum_{l_2=1}^n … \sum_{l_k=1}^n \left(\gcd\left(l_1,l_2,…,l_k\right)\right)^2\cr
&=\sum_d\sum_{l_1=1}^{\left\lfloor\frac{n}{d}\right\rfloor} \sum_{l_2=1}^{\left\lfloor\frac{n}{d}\right\rfloor} … \sum_{l_k=1}^{\left\lfloor\frac{n}{d}\right\rfloor} \left[\gcd\left(l_1,l_2,…,l_k\right)=1\right]\cdot d^2\cr
&=\sum_dd^2\sum_{l_1=1}^{\left\lfloor\frac{n}{d}\right\rfloor} \sum_{l_2=1}^{\left\lfloor\frac{n}{d}\right\rfloor} … \sum_{l_k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\ \ \sum_{t|\gcd(l_1,l_2,\cdots,l_k)}\mu(t)\cr
&=\sum_dd^2\sum_{t=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(t)\cdot \left\lfloor\frac{n}{td}\right\rfloor^k
\end{aligned}

设 T=td：

\begin{aligned}
f_n(k)&=\sum_{T=1}^n\left\lfloor\frac{n}{T}\right\rfloor^k\sum_{t|T}\mu(t)\left(\frac{T}{t}\right)^2\cr
\therefore ans&=\sum_{i=2}^{k}\sum_{T=1}^n\left\lfloor\frac{n}{T}\right\rfloor^i\sum_{t|T}\mu(t)\left(\frac{T}{t}\right)^2\cr
&=\sum_{T=1}^{n}\left(\sum_{i=2}^k\left\lfloor\frac{n}{T}\right\rfloor^i\right)\left(\sum_{t|T}\mu(t)\left(\frac{T}{t}\right)^2\right)
\end{aligned}

设：g(T)=\sum_{t|T}\mu(t)\left(\frac{T}{t}\right)^2=\mu(T) * id^2(T)

则有：g(T) * I(T)=\mu(T) * I(T) * id^2(T)=\varepsilon(T) * id^2(T)=id^2(T)

因此 g(T) 可杜教筛。线性筛部分，T 为质数时，易知 g(T)=T^2-1 。

T=p^c，g(T)=T^2+\mu(p)\cdot\frac{T^2}{p^2}=p^2\left(p^{2c}-p^{2c-2}\right)

T=p^{c+1}，g(T)=T^2+\mu(p)\cdot\frac{T^2}{p^2}=p^2\left(p^{2c+2}-p^{2c}\right)

T=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}，

g(T\cdot p_1)=g\left(p_1^{k_1+1}\cdot\frac{T}{p_1^{k_1}}\right)=g\left(p_1^{k_1+1}\right)\cdot g\left(\frac{T}{p_1^{k_1}}\right)\ \ \ (两部分互质)

g(T)=g\left(p_1^{k_1}\cdot\frac{T}{p_1^{k_1}}\right)=g\left(p_1^{k_1}\right)\cdot g\left(\frac{T}{p_1^{k_1}}\right)

\therefore g(T\cdot p_1)=g(T)\cdot p^2

前半部分为等比数列求和，可整除分块。要特别注意，特判 \left\lfloor\frac{n}{T}\right\rfloor=1 的情况，这时候的 k 对 P 取模；其他情况，k 位于指数上，要对 \varphi(P) 取模。因此要在读入时取得两个不同的 k 值。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 50;
const int P = 1e9 + 7;
const int PHI = 1e9 + 6;
int inv6;
int T, n, k_phi, k_mod;

unordered_map<int, int> Sumg;
int p[N], num[N], tot;
int sumg[N];

void getmod() {
    long long b = 0, b2 = 0; char c;
    while (!isdigit(c = getchar()));
    for (;isdigit(c); c = getchar()) {
        b = b * 10 + c - '0'; b2 = b2 * 10 + c - '0';
        if (b >= PHI) b %= PHI;
        if (b2 >= P) b2 %= P;
    }
    k_phi = int(b); k_mod = int(b2);
}

int ksm(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1, a = 1LL * a * a % P) if (b & 1) {
        ret = 1LL * ret * a % P;
    }
    return ret;
}
int ni(int a) {
    return ksm(a, P - 2);
}
inline void add(int &a, int b) {
    a += b; if (a > P) a -= P;
}
inline void del(int &a, int b) {
    a -= b; if (a < 0) a += P;
}

void init() {
    sumg[1] = 1;
    for (int i = 2; i < N; i++) {
        if(!num[i]) {
            p[++tot] = i;
            sumg[i] = (1LL * i * i - 1) % P;
        }
        for (int j = 1, x; j <= tot && (x = i * p[j]) < N; j++) {
            num[x] = 1;
            if (i % p[j]) sumg[x] = 1LL * sumg[i] * sumg[p[j]] % P;
            else {
                sumg[x] = 1LL * sumg[i] * p[j] % P * p[j] % P;
                break;
            }
        }
    }
    for(int i = 1; i < N; i++) add(sumg[i], sumg[i - 1]);
    inv6 = ni(6);
}

inline int Ssqr(int n) {
    return 1LL * n * (n + 1) % P * (2 * n + 1) % P * inv6 % P;
}

int Getsumg(int n) {
    if(n < N) return sumg[n];
    if (Sumg.count(n)) return Sumg[n];
    int ret = Ssqr(n);
    for(int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        del(ret, 1LL * (r - l + 1) * Getsumg(n / l) % P);
    }
    return Sumg[n] = ret;
}

int sum_k(int n) { // 等比数列求和
    if(n == 1) return k_mod - 1;
    int ret = ksm(n, k_phi + 1);
    del(ret, 1LL * n * n % P);
    ret = 1LL * ret * ni(n - 1) % P;
    return ret;
}

int solve() {
    int ans = 0;
    for(int l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        int x = sum_k(n / l), y = (Getsumg(r) - Getsumg(l - 1) + P);
        add(ans, 1LL * x * y % P);
    }
    return ans;
}

int main() {
    init();
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n); getmod();
        printf("%d\n", solve());
    }
    return 0;
}