题解 P6156 【简单题】
CYJian
·
·
题解
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 的数值来计算 f(x) 了。
```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;
}
```