自动搬运

查看原文

来自洛谷，原作者为

	chroneZ **

搬运于2025-08-24 22:46:40，当前版本为作者最后更新于2023-05-04 18:36:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

首先可以发现，我们可以从 $1$ 到 $n$ 枚举位置，如果该位上的硬币朝下，则将该硬币连同其倍数位置的硬币全部翻转。这样做是 $\mathcal{O}(n \log n)$ 的。

记 $f(i)$ 表示递推过程中考虑到硬币 $i$ 时它是否需要被翻转（下文所有的 $f(i)$ 都是模 $2$ 意义下的），容易得到 $f(i) = \sum \limits_{d | i, d \neq i} f(d)$。

显然硬币 $1$ 一定会被翻转，因此 $f(1) = 1$。我们最终要求的其实就是 $f$ 函数的前缀和。

因为除硬币 $1$ 外，所有硬币最初就是朝上的，因此 $\sum \limits_{d | i} f(d) = \epsilon(i)$。写作 Dirichlet 卷积形式就是 $1 * f = \epsilon$，反演一下得 $f = \epsilon * \mu = \mu$。由定义，若 $f(i) = \mu(i) = -1$ 时，令 $f(i) \gets 1$ 即可等效。至此问题化归为，求

$$\sum \limits_{i = 1} ^ n \mu^2(i)$$

联系 $\mu^2(i)$ 的实际意义，我们知道该值表示 $i$ 是否含有平方因子（$\text{e.g. }\mu^2(i) = 1$ 表示 $i$ 不具有平方因子）。直接枚举这些平方因子，并再对 $\epsilon$ 作一次反演可以得到

$$\mu^2(i) = \sum_{d^2|i} \mu(d)$$

当然，换一种更加具体的理解方式，考虑对 $i$ 唯一分解得 $i = \prod p_i ^{k_i}$，并令 $P = \prod p_i ^{ \lfloor \frac{k_i}{2} \rfloor}$，则 $i$ 不含平方因子等价于 $P = 1$，因此有 $\mu^2(i) = \epsilon(P) = \sum \limits_{d | P} \mu(d)$，可以证明此式和上式是等价的。

由此结论，考虑每个完全平方数对答案的贡献，可以推得 $\sum \limits_{i = 1} ^ n \mu^2(i) = \sum \limits_{i = 1} ^ {\sqrt n} \mu(i)\lfloor \frac{n}{i ^ 2} \rfloor$，利用预处理 + 杜教筛可以求 $\sum \mu(i)$，对后面的 $\lfloor \frac{n}{i^2} \rfloor$ 整除分块即可。高次整除分块的形式是 $r \gets \lfloor \sqrt{\lfloor\frac{n}{\lfloor \frac{n}{l^2} \rfloor}\rfloor} \rfloor$。

---

略提一下时间复杂度分析。

首先 $\lfloor \frac{n}{i ^ 2} \rfloor$ 会有 $\mathcal{O}(n ^ {\frac{1}{3}})$ 种取值，证明很简单，如果 $i \geq n ^ {\frac{1}{3}}$，则 $1 \leq \lfloor \frac{n}{i ^ 2} \rfloor \leq n ^ {\frac{1}{3}}$，只有 $n ^ {\frac{1}{3}}$ 种取值；如果 $i \leq n ^ {\frac{1}{3}}$，这样的 $i$ 只会有 $n ^ {\frac{1}{3}}$ 个，因此其对应的 $\lfloor \frac{n}{i ^ 2} \rfloor$ 也只有 $n ^ {\frac{1}{3}}$ 个。

由这个证明可以推得整除分块的“分界点”（即 $r$ 的可能取值）近似为 $1, 2, \dots, n ^ {\frac{1}{3}}, \sqrt{\lfloor \frac{n}{n ^ {\frac{1}{3}}}\rfloor}, \sqrt{\lfloor \frac{n}{n ^ {\frac{1}{3}} - 1}\rfloor}, \dots, \sqrt{\lfloor \frac{n}{1} \rfloor}$，因为如果存在 $i$ 使得 $\lfloor \frac{n}{i ^ 2} \rfloor = x$，则一定有一个解为 $i = \sqrt{\lfloor \frac{n}{x}\rfloor}$。但是在 $1 \leq x \leq n ^ {\frac{1}{3}}$ 的枚举过程中，可能根本不存在一个 $i$ 使得 $\lfloor \frac{n}{i ^ 2} \rfloor = x$，这就会产生增解。考虑到增解的数量很少，因此将其近似地忽略掉。

仿照杜教筛时间复杂度的证明过程，考虑预处理 $[1, n ^ {c}](c > \frac{1}{3})$ 内的 $\mu$ 函数前缀和，需要杜教筛的部分缩小为 $\sqrt{\lfloor \frac{n}{n ^ {1 - 2c}}\rfloor}, \dots, \sqrt{\lfloor \frac{n}{1}\rfloor}$。为了便于计算复杂度，这里将其近似看作 ${\lfloor \frac{\sqrt n}{n ^ {\frac{1}{2} - c}}\rfloor}, \dots, {\lfloor \frac{\sqrt n}{1}\rfloor}$（仅仅是数值相近，而非二者真的等价）。从这里可以知道杜教筛次数的上界为 $\mathcal{O}(n ^ {\frac{1}{2} - c})$，每次筛的复杂度为

$$\mathcal{O}(\sum \limits_{i = 1} ^ {n ^ {\frac{1}{2} - c}} \sqrt{\lfloor \frac{\sqrt n}{ i} \rfloor}) = \mathcal{O}(\int_{1} ^ {n ^ {\frac{1}{2} - c}} \sqrt{\frac{\sqrt n}{x}} dx) $$

这一步是积分近似，解这个积分得

$$F(x) = 2n ^ {\frac{1}{4}}x ^{\frac{1}{2}}$$

将 $x = n ^ {\frac{1}{2} - c}$ 代入，得 $2n^{\frac{1}{2} - \frac{1}{2}c}$，因此每次杜教筛的复杂度是 $\mathcal{O}(n ^ {\frac{1}{2} - \frac{1}{2} c})$。

综上所述，总复杂度 $\mathcal{O}(n ^ c + n ^ {\frac{1}{2} - c} \cdot n ^ {\frac{1}{2} - \frac{1}{2} c}) = \mathcal{O}(n ^ c + n ^ {1 - \frac{3}{2} c})$，取 $c = \frac{2}{5}$ 时复杂度最优，为 $\mathcal{O}(n ^ {\frac{2}{5}})$。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

constexpr int N = 1e9 + 10, M = 1.6e7;

int lim;

vector<int> pr;
int vis[M], mu[M], S1_mu[M];

void sieve(){
	mu[1] = 1;
	for(int i = 2; i <= lim; i++){
		if(!vis[i]) pr.push_back(i), mu[i] = -1;
		for(int j = 0; j < pr.size() && pr[j] * i <= lim; j++){
			vis[pr[j] * i] = 1;
			if(i % pr[j] == 0){
				mu[pr[j] * i] = 0;
				break;
			}
			mu[pr[j] * i] = -mu[i];
		}
	}
	for(int i = 1; i < lim; i++)
		S1_mu[i] = S1_mu[i - 1] + mu[i];
}

unordered_map<int, int> S2_mu;

int S_mu(int n){
	if(n <= lim) return S1_mu[n];
	auto it = S2_mu.find(n);
	if(it != S2_mu.end()) return it->second;

	int res = 1;
	for(int l = 2, r; l <= n; l = r + 1){
		r = n / (n / l);
		res -= (r - l + 1) * S_mu(n / l);
	}
	return S2_mu[n] = res;
}

int main(){
	ios::sync_with_stdio(false); 
	cin.tie(nullptr); cout.tie(nullptr);
	
	i64 n; cin >> n;
	lim = powl(n, 2.0 / 5) + 10;
	
	sieve();
	
	i64 m = sqrtl(n);

	i64 ans = 0, pre = 0, cur;
	for(i64 l = 1, r; l <= m; l = r + 1){
		r = sqrtl(n / (n / (l * l)));
		ans += (S_mu(r) - S_mu(l - 1)) * (n / (l * l));
	}
	cout << ans << "\n";
}