自动搬运

查看原文

来自洛谷，原作者为

	CYJian 今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました

搬运于2025-08-24 22:18:43，当前版本为作者最后更新于2020-03-21 15:28:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

搬运

如果这个加强版有什么问题请私信戳我。

---

这个题推柿子的部分较为简单，就简单写写吧。

$$\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$：

const int MAXN = 20000010;

inline uit fsp(uit x, int k) {
	uit s = 1;
	while(k) {
		if(k & 1) s *= x;
		x *= x, k >>= 1;
	} return s;
}

int tot;
int pri[MAXN / 10];
bitset<MAXN>chk;
uit f[MAXN];
uit 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;
		for(int j = 1; j <= tot; j++) {
			if(i * pri[j] > n) break;
			int p = i * pri[j];
			chk[p] = 1;
			F[p] = F[i] * F[pri[j]];
			if(i % pri[j] == 0) {
				int q = i / pri[j];
				if(q % pri[j]) f[p] = -pri[j] * f[q];
				break;
			} f[p] = f[i] * (pri[j] - 1);
		}
	}
	for(int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i] * F[i], F[i] += F[i - 1];
	for(int i = 2; i <= n; i++) F[i] += F[i - 1];
}

inline uit Calc(int n) { return F[n << 1] - (F[n] << 1); }

int main() {
#ifdef LOCAL
	FILE("");
#endif
	int Case = ri, N = ri, k = ri;
	Sieve(N << 1, k);
	while(Case--) {
		uit res = 0;
		int n = ri;
		for(int l = 1, r; l <= n; l = r + 1) {
			r = n / (n / l);
			res += (f[r] - f[l - 1]) * Calc(n / l);
		} cout << res << "\n";
	}
	return 0;
}