2020 Multi-University Training Contest 6 （杭电多校） 1007

问：

[sum_{a_{1}=1}^{n} sum_{a_{2}=1}^{n} ldots sum_{a_{x}=1}^{n}left(prod_{j=1}^{x} a_{j}^{k} ight) fleft(operatorname{gcd}left(a_{1}, a_{2}, ldots, a_{x} ight) ight) cdot operatorname{gcd}left(a_{1}, a_{2}, ldots, a_{x} ight) ]

答：

先令 (g = gcd(a_1, a_2 cdots , a_x), F(x) = f(x)x)。

由莫比乌斯反演有：

[H = F * mu ]

（具体怎么计算 (H) 后文有）则 (F = H * 1)。

那么原式子等价于：

[egin{array} = &sum_{a_{1}=1}^{n} sum_{a_{2}=1}^{n} ldots sum_{a_{x}=1}^{n}left(prod_{j=1}^{x} a_{j}^{k} ight) fleft(operatorname{gcd}left(a_{1}, a_{2}, ldots, a_{x} ight) ight) cdot operatorname{gcd}left(a_{1}, a_{2}, ldots, a_{x} ight) \ = &sum_{a_{1}=1}^{n} sum_{a_{2}=1}^{n} ldots sum_{a_{x}=1}^{n}left(prod_{j=1}^{x} a_{j}^{k} ight) F(g) \ = &sum_{a_{1}=1}^{n} sum_{a_{2}=1}^{n} ldots sum_{a_{x}=1}^{n}left(prod_{j=1}^{x} a_{j}^{k} ight) sum_{d | g} H(d) \ = & sum_{a_{1}=1}^{n} sum_{a_{2}=1}^{n} ldots sum_{a_{x}=1}^{n}left(prod_{j=1}^{x} a_{j}^{k} ight) sum_{d = 1}^n H(d) [d | g] \ = & sum_{d = 1}^n H(d) (sum_{a_{1}=1}^{n}a_1^k[d|a_1]) (sum_{a_{2}=1}^{n}a_2^k[d|a_2]) ldots (sum_{a_{x}=1}^{n} a_x^k[d|a_x]) \ = & sum_{d = 1}^n H(d) sum_{a_{1}=1}^{lfloor frac{n}{d} floor} (a_1d)^k sum_{a_{2}=1}^{lfloor frac{n}{d} floor} (a_2d)^k ldots sum_{a_{x}=1}^{lfloor frac{n}{d} floor} (a_xd)^k \ = & sum_{d = 1}^n H(d) [sum_{i = 1}^{lfloor frac{n}{d} floor} (id)^k]^x \ = & sum_{d = 1}^n H(d)d^{kx} [sum_{i = 1}^{lfloor frac{n}{d} floor} i^k]^x end{array} ]

那么，令 (S(d) = sum_{i = 1}^d i^k, T(d) = H(d) imes d^{kx})，那么上式等价于：

[sum_{d = 1}^n T(d)S^x(lfloor n / d floor) ]

显然，(S(d)) 是可以预处理出来的，且套用数论分块就能求出上面的式子。那么现在的关键就是怎么求 (H(d)) 。

由于

[H(x) = F * mu = sum_{d | x} F(x)mu(frac{x}{d}) = sum_{d | x}df(d)mu(frac{x}{d}) = sum_{d | x}dmu^2(d)mu(frac{x}{d}) ]

注意到这是个积性函数，那么我们可以考虑如何用线性筛来求得上面的函数。

1.当 (x) 是质数，也就是 (x = p) 时
$$
H(p) = 1 mu^2(1)mu(p) + pmu^2(p)mu(1) = p - 1
$$

2.当 (x) 不是质数，但 (x = a imes p)，且 (a) 与 (p) 互质时，由积性函数有
$$
H(a imes p) = H(a) imes H(p)
$$

3.当 (x) 不是质数，但 (x = a imes p)，且 (a) 与 (p) 不互质时，令 (a = b imes p^{t - 1})，其中 (b) 与 (p) 互质，那么就有
$$
H(a imes p) = H(b imes p^t) = H(b) imes H(p^t) quad (t ge 2)
$$
注意到
$$
H(p^t) = sum_{d | p^t}dmu2(d)mu(frac{p^t}{d}) = sum_{t_1 = 0}^t p^{t_1}mu2(p^{t_1})mu(p{t_2}) quad (t_1 + t_2 = t)
$$
中，当且仅当 (t_1 = t_2 = 1quad (t = 2)) 时，(H(p^t) = -p)，其他时候 (H(p^t) = 0)

所以，利用线性筛，能在 (O(nlog n)) 的时间内预处理出 (H(x), T(x), S(x))。然后每次询问，利用数论分块求和。总的时间复杂度为：(O(nlog n + T sqrt n))

参考代码：

#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x) * (x))
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
typedef long long ll;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 7;
using namespace std;
int h[maxn], prime[maxn], tmp[maxn];
int mod = 1e9 + 7;
int sum[maxn], T, k, x;
bool check[maxn];
int tot = 0;
ll qpow(ll a, ll n) {
    ll ans = 1;
    for (a %= mod; n; n >>= 1) {
        if (n & 1) ans = a * ans % mod;
        a = a * a % mod;
    }
    return ans;
}
void init(int n) {
    h[1] = 1;
    tot = 0;
    for (int i = 2; i <= n; i++) {
        if (!check[i]){
            prime[tot++] = i;
            h[i] = i - 1;
        }
        for (int j = 0; j < tot && prime[j] * i <= n; j++) {
            check[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                int cnt = 1, x = i;
                while (x % prime[j] == 0) {
                    cnt++;
                    x /= prime[j];
                }
                if (cnt == 2)
                    h[i * prime[j]] = (-1ll * prime[j] * h[x] % mod + mod) % mod;
                else
                    h[i * prime[j]] = 0;
                break;
            } else {
                h[i * prime[j]] = 1ll * h[i] * h[prime[j]] % mod;
            }
        }
    }

    for (int i = 1; i <= n; i++) sum[i] = (sum[i - 1] + qpow(i, k)) % mod;
    for (int i = 1; i <= n; i++){
        tmp[i] = h[i] * qpow(i, 1ll * k * x %(mod - 1)) % mod;
        tmp[i] = (tmp[i] + tmp[i - 1]) % mod;
        sum[i] = qpow(sum[i], x);
    }
}

int main(void) {
#ifdef ljxtt
    freopen("data.in", "r", stdin);
#endif
    scanf("%d%d%d", &T, &k, &x);
    init(maxn - 1);
    while (T--) {
        int n;
        scanf("%d", &n);
        ll ans = 0;
        for(int i = 1, r; i <= n; i = r + 1){
            r = min(n, n / (n / i));
            ans = (ans + 1ll * (tmp[r] - tmp[i - 1] + mod) % mod * sum[n / i] % mod) % mod;
        }
        ans = (ans % mod + mod) % mod;
        printf("%lld
", ans);
    }
    return 0;
}