题解 P6156 【简单题】

CYJian

2020-03-18 15:37:10

Solution

yysy,这个题出的不太到位。 存在 $O(n)$ 预处理 $O(\sqrt n)$ 单次询问的做法,多测不香么...反倒放了暴力 $O(n^{3/4})$ 过... --- 这个题推柿子的部分较为简单,就简单写写吧。 $$\sum_{i=1}^{n}\sum_{j=1}^{n} (i+j)^k \mu^2((i,j))(i,j)$$ $$\sum_{d=1}^{n}\mu^2(d)d^{k+1}\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}(i+j)^k[(i,j)=1]$$ $$\sum_{d=1}^{n}\mu^2(d)d^{k+1}\sum_{t=1}^{n/d}\mu(t)t^k\sum_{i=1}^{n/td}\sum_{j=1}^{n/td} (i+j)^k$$ 令 $S(x)=\sum_{i=1}^{x}\sum_{j=1}^{x} (i+j)^k$。 $$ \sum_{d=1}^{n}\sum_{t=1}^{n/d}t^kd^{k+1}\mu(t)\mu^2(d)S(\frac{n}{td}) $$ 令 $T = td$: $$ \sum_{T=1}^{n}T^kS(\frac{n}T)\sum_{d|T}d\mu^2(d)\mu(\frac{T}{d}) $$ --- 然后考虑快速预处理需要的东西: 先考虑快速求 $S(x)$: 令 $F(n) = \sum_{i=1}^{n} i^k$,$G(n) = \sum_{i=1}^{n}F(i)$。 则有:$S(n) = \sum_{i=n+1}^{2n}F(i)-\sum_{i=1}^{n}F(i)=G(2n)-2G(n)$。 自然数 $k$ 次幂可以 $O(n)$ 用欧拉筛筛出来。 然后一次前缀和求 $F(x)$ 之后,再做前缀和就能求 $S(x)$ 了。 再考虑 $f(n) = \sum_{d|n}d \mu^2(d)\mu(\frac{n}{d})$:由于是一堆积性函数的狄利克雷卷积的形式,则 $f(n)$ 也一定是积性函数。 考虑欧拉筛筛中 $x$ 时,枚举到的质因数是 $p$。从 $\mu$ 函数着手考虑,则讨论 $p$ 在 $x$ 中的最高次幂因子:假设 $p^k \mid x$ 且有 $p^{k+1} \nmid x$: 根据积性函数性质,则有:$f(x) = f(p^k) \times f(\frac{x}{p^k})$。 讨论一下 $f(p^k)$ 的取值: - $k=0$,即 $f(1)$ 的取值一定为 $1$。 - $k=1$,则 $f(p) = 1 \mu^2(1) \mu(p) + p \mu^2(p) \mu(1) = p-1$。 - $k=2$,则 $f(p^2) = 1 \mu^2(1) \mu(p^2) + p \mu^2(p) \mu(p) + p^2 \mu^2(p^2) \mu(1)=-p$。 - $k \ge 3$,由于鸽笼原理,此时 $d$ 和 $\frac{x}{d}$ 中至少有一个能被 $p^2$ 整除,则那一个的 $\mu$ 的值为 $0$。所以此时 $f(p^k)=0$。 然后就可以通过判断 $k$ 的数值来计算 $f(x)$ 了。 $\rm Code$: ```cpp const int MAXN = 10000010; const int mod = 998244353; inline int Mod(int x) { return x >= mod ? x - mod : x; } inline void Add(int&x, int y) { x += y, x -= x >= mod ? mod : 0; } inline int fsp(int x, int k) { int s = 1; while(k) { if(k & 1) s = 1LL * s * x % mod; x = 1LL * x * x % mod, k >>= 1; } return s; } int tot; int pri[MAXN / 10]; bitset<MAXN>chk; int f[MAXN]; int F[MAXN]; inline void Sieve(int n, int k) { f[1] = F[1] = 1; for(int i = 2; i <= n; i++) { if(!chk[i]) pri[++tot] = i, f[i] = i - 1, F[i] = fsp(i, k); for(int j = 1; j <= tot; j++) { if(i * pri[j] > n) break; int p = i * pri[j]; chk[p] = 1; F[p] = 1LL * F[i] * F[pri[j]] % mod; if(i % pri[j] == 0) { int q = i / pri[j]; if(q % pri[j]) f[p] = 1LL * (mod - pri[j]) * f[q] % mod; break; } f[p] = 1LL * f[i] * (pri[j] - 1) % mod; } } for(int i = 2; i <= n; i++) f[i] = (f[i - 1] + 1LL * f[i] * F[i]) % mod, Add(F[i], F[i - 1]); for(int i = 2; i <= n; i++) Add(F[i], F[i - 1]); } inline int Calc(int n) { return Mod(F[n << 1] + mod - Mod(F[n] << 1)); } int main() { int n = ri, k = rl % (mod - 1), res = 0; Sieve(n << 1, k); for(int l = 1, r; l <= n; l = r + 1) { r = n / (n / l); res = (res + 1LL * (f[r] - f[l - 1] + mod) * Calc(n / l)) % mod; } cout << res << endl; return 0; } ```