[蓝桥杯 2023 省 A] 翻转硬币

形式化题目

有 $n$ 个位置 $1,2,\dots,n$ 。初始状态为位置 $1$ 是 $0$ （朝下），其余位置是 $1$ （朝上）。一次操作选定一个整数 $i$ ，把所有下标是 $i$ 的倍数的位置取值翻转（ $0\leftrightarrow 1$ ）。求把所有位置都变成 $1$ 所需的最少操作次数。

由于同一种操作做两次等于没做，我们只需决定每个 $i$ 做 $0$ 次还是 $1$ 次，即求一个子集 $S\subseteq\{1,\dots,n\}$ 使所有位置最终为 $1$ ，并最小化 $|S|$ 。（严格说：把任意方案里每个操作的重数模 $2$ 后再执行，每个位置被翻转次数的奇偶性不变，所以一定存在只含 $0/1$ 次的最优方案，下面只讨论 $0/1$ 方案。）下标 $i>n$ 的操作不会影响 $1..n$ 中任何位置，因此只需考虑 $i\leqslant n$ 。

解法路线

题面给的是一组真实的分层约束： $30\%$ 的数据 $n\leqslant 5\times10^6$ ， $70\%$ 的数据 $n\leqslant 10^9$ ，全部数据 $n\leqslant 10^{18}$ 。三层各自的瓶颈完全不同，因此本文按子任务递进组织，每一层复用上一层的关键结论，只换掉受限的那一步：

层次	适用范围	核心做法	瓶颈
暴力解法	$n\leqslant 5\times 10^6$	按定义标记含平方因子的数	必须遍历 $1..n$ 每个数
子任务解法	$n\leqslant 10^9$	容斥公式 + 枚举 $d\leqslant\sqrt n$	枚举量 $\sqrt n$ ， $n=10^9$ 时是 $3\times10^4$ ，但 $n=10^{18}$ 时涨到 $10^9$
正解	$n\leqslant 10^{18}$	对 $d$ 分块 + 杜教筛求莫比乌斯前缀和	块数 $n^{1/5}$ ，线性筛规模 $n^{2/5}$

正式主解是第三层，代码为 main.cpp。

暴力解法

适用范围

$n\leqslant 5\times 10^6$ ，对应题面 $30\%$ 的评测用例。

思路

先解决「答案是什么」这个问题，三种规模都共用它。

令 $x_i\in\{0,1\}$ 表示是否执行操作 $i$ 。位置 $j$ 被翻转的总次数是

\sum_{i\mid j} x_i

要求位置 $j$ 最终朝上，也就是被翻转偶数次；位置 $1$ 初始朝下，要求被翻转奇数次：

\begin{cases} x_1 = 1 \pmod 2, & j=1\\[2pt] \displaystyle\sum_{i\mid j} x_i = 0 \pmod 2, & j\geqslant 2 \end{cases}

关键在于这个方程组的解是唯一的。按 $j$ 从小到大看第 $j$ 个方程：其中出现的 $x_i$ 都满足 $i\mid j$ ，于是 $i\leqslant j$ ；除了 $x_j$ 自己，其余 $x_i$ 的下标都严格小于 $j$ ，已经确定。 $x_j$ 的系数是 $1$ ，模 $2$ 下可逆，所以 $x_j$ 被唯一确定。

既然解唯一，「最少操作次数」就不是一个需要搜索的最优化问题，而是这个唯一解的重量。把解写出来：莫比乌斯函数满足

\sum_{d\mid j}\mu(d) = [\,j=1\,]

这正好就是上面两组方程（ $j=1$ 时等号右边是 $1$ ， $j\geqslant2$ 时是 $0$ ），所以唯一解就是 $x_i=\mu(i)$ ，方案里被选中的下标恰好是那些 $\mu(i)\neq0$ 的 $i$ ，也就是不含平方因子的数。于是

\text{答案} = \#\{\,i\leqslant n : \mu(i)\neq 0\,\}

以 $n=7$ 为例， $\mu$ 的取值如下：

$i$	1	2	3	4	5	6	7
$\mu(i)$	$1$	$-1$	$-1$	$0$	$-1$	$1$	$-1$
是否操作	是	是	是	否	是	是	是

$\mu(i)\neq0$ 的有 $1,2,3,5,6,7$ 共 $6$ 个，答案就是 $6$ ：唯一解是操作集合 $\{1,2,3,5,6,7\}$ ；而 $4$ 含平方因子 $2^2$ ，代入 $\mu(4)=0$ 表示不用操作 $4$ （操作 $1,2$ 已经把它翻回朝上）。可以逐位验证，这个集合确实让全部 $7$ 枚硬币朝上。

剩下的事就是统计 $1..n$ 里有多少个无平方因子数。暴力做法是最贴定义的：对每个素数 $p\leqslant\sqrt n$ ，把 $p^2$ 的所有倍数都打上「含平方因子」标记，最后没被标记过的数个数就是答案。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:07
 * update_at: 2026-10-02 15:07
 */
/*
 * brute.cpp：小数据暴力解，用来辅助对拍。
 *
 * 思路：完全不用莫比乌斯函数，直接按定义统计无平方因子数。
 * 对每个素数 p <= sqrt(n)，把 p^2 的所有倍数都标记成「含平方因子」，
 * 最后没被标记过的数就是无平方因子数，答案就是它们的个数。
 * 复杂度 O(n)，适合 n <= 2e7 的对拍规模。
 *
 * 它和 main.cpp 的莫比乌斯 + 杜教筛路线没有任何共享逻辑，
 * 是一个可以独立验证结论的暴力。
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20000005;
static char bad[MAXN];    // bad[x] = 1 表示 x 含平方因子
static int primes[1500000];
int pcnt;

int main() {
    int n;
    scanf("%d", &n);

    // 线性筛出 sqrt(n) 以内的素数
    int lim = (int)sqrt((double)n) + 1;
    vector<char> isc(lim + 1, 0);
    for (int i = 2; i <= lim; i++) {
        if (!isc[i]) primes[++pcnt] = i;
        for (int j = 1; j <= pcnt; j++) {
            long long v = (long long)primes[j] * i;
            if (v > lim) break;
            isc[(int)v] = 1;
            if (i % primes[j] == 0) break;
        }
    }

    // 把每个 p^2 的倍数标记为「含平方因子」
    for (int j = 1; j <= pcnt; j++) {
        long long sq = (long long)primes[j] * primes[j];
        for (long long x = sq; x <= n; x += sq) {
            bad[(int)x] = 1;
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!bad[i]) ans++;
    }

    printf("%lld\n", ans);
    return 0;
}

复杂度与瓶颈

时间复杂度： $O(n)$ ，标记 $p^2$ 倍数的总次数为 $\sum_{p\leqslant\sqrt n}\!\lfloor n/p^2\rfloor<0.46\,n$ ，再加上 $O(\sqrt n)$ 的素数筛和 $O(n)$ 的一次计数。
空间复杂度： $O(n)$ ，用一个 char 数组记录每个数是否含平方因子。

$n\leqslant5\times10^6$ 时这个做法轻松通过，但它要逐个访问 $1..n$ 的每一个数， $n=10^{18}$ 时根本开不下数组，也不可能跑完。下一步必须把「数出无平方因子数」换成一个只依赖 $n$ 的算术式子。

子任务解法： $n\leqslant 10^9$

适用范围

$n\leqslant 10^9$ ，对应题面 $70\%$ 的评测用例（它同时覆盖了上一层的 $n\leqslant5\times10^6$ ，只是标记法换成公式）。

思路

把「无平方因子」写成容斥。对每个 $d$ ，被 $d^2$ 整除的数有 $\lfloor n/d^2\rfloor$ 个，用莫比乌斯函数作容斥系数就得到无平方因子数的个数：

Q(n)=\sum_{d=1}^{\lfloor\sqrt n\rfloor}\mu(d)\left\lfloor\frac{n}{d^2}\right\rfloor

这个式子的正确性由 $\mu$ 的定义直接给出： $[\,m\text{ 无平方因子}\,]=\sum_{d^2\mid m}\mu(d)$ ，对 $m=1..n$ 求和并交换求和次序， $d$ 的可取范围就是 $d^2\leqslant n$ ，即 $d\leqslant\lfloor\sqrt n\rfloor$ 。

$n\leqslant10^9$ 时 $\lfloor\sqrt n\rfloor\leqslant31622$ ，线性筛出 $\mu(1..31622)$ ，然后一项一项累加即可。注意每一项 $\lfloor n/d^2\rfloor$ 必须用整除， $d^2$ 要用 long long 计算，避免 $d\approx3\times10^4$ 时 $d^2$ 溢出 int。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:07
 * update_at: 2026-10-02 15:07
 */
/*
 * 子任务解法：n <= 1e9（对应题面 70% 的评测用例）。
 *
 * 直接使用容斥公式 Q(n) = sum_{d=1}^{floor(sqrt(n))} mu(d) * floor(n / d^2)。
 * n <= 1e9 时 sqrt(n) <= 31623，线性筛出 mu 后直接枚举 d 即可，
 * 复杂度 O(sqrt(n))，和 main.cpp 的杜教筛路线相比只是少了「d 很大」这一段。
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXM = 40000;     // n <= 1e9 时 sqrt(n) <= 31623
static int mu[MAXM];
static int primes[MAXM];
static char isc[MAXM];
int pcnt;

int main() {
    ll n;
    scanf("%lld", &n);

    int N = (int)sqrtl((long double)n) + 1;
    if (N > MAXM - 1) N = MAXM - 1;

    // 线性筛莫比乌斯函数
    mu[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!isc[i]) {
            primes[++pcnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= pcnt; j++) {
            ll v = (ll)primes[j] * i;
            if (v > N) break;
            isc[v] = 1;
            if (i % primes[j] == 0) {
                mu[v] = 0;
                break;
            }
            mu[v] = -mu[i];
        }
    }

    // 直接枚举所有 d <= sqrt(n)
    ll ans = 0;
    for (ll d = 1; d <= N; d++) {
        ans += (ll)mu[d] * (n / (d * d));
    }

    printf("%lld\n", ans);
    return 0;
}

复杂度与瓶颈

时间复杂度： $O(\sqrt n)$ ，线性筛 $O(\sqrt n)$ 加一次枚举 $O(\sqrt n)$ 。
空间复杂度： $O(\sqrt n)$ 。

$n\leqslant10^9$ 时枚举量只有 $3\times10^4$ ，很快。但 $n\leqslant10^{18}$ 时 $\sqrt n=10^9$ ，一次枚举就是十亿项，依然过不了。瓶颈变成了求和项数太多，而每一项的值 $\lfloor n/d^2\rfloor$ 会随着 $d$ 变大而迅速变小——这说明大量的项取到相同的值，可以合并。

正解

关键观察

$\lfloor n/d^2\rfloor$ 只有 $O(n^{1/3})$ 个不同取值，而且 $d$ 越大、取值越小、重复越密集。把取值同为 $q$ 的那些 $d$ 放在一起处理，就能把「枚举 $d$ 」压成「枚举 $q$ 」。具体地， $d\in(\lfloor\sqrt{n/(q+1)}\rfloor,\ \lfloor\sqrt{n/q}\rfloor]$ 时恰好 $\lfloor n/d^2\rfloor=q$ ，这一段的和是

q\cdot\Big(M\big(\lfloor\sqrt{n/q}\rfloor\big)-M\big(\lfloor\sqrt{n/(q+1)}\rfloor\big)\Big),\qquad M(x)=\sum_{i=1}^{x}\mu(i)

其中 $M$ 就是莫比乌斯前缀和。于是问题变成两件事：块数能不能压得更少，以及怎么快速求 $M$ 。

对第二件事用杜教筛。由 $\mu*I=\varepsilon$ （即 $\sum_{d\mid m}\mu(d)=[m=1]$ ）对 $m=1..x$ 求和：

1=\sum_{m=1}^{x}\sum_{d\mid m}\mu(d)=\sum_{d=1}^{x}M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right)

把 $d=1$ 那一项单独拎出来（它是 $M(x)$ ），就得到递推式

M(x)=1-\sum_{d=2}^{x}M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right)

右边按 $\lfloor x/d\rfloor$ 的取值分块，配合 unordered_map 记忆化，单次求 $M(x)$ 的复杂度是 $O(x^{2/3})$ 。

对第一件事做权衡：设前 $T$ 个 $d$ 直接线性筛加枚举， $d>T$ 的部分按 $q$ 分块，块数

Q=\left\lfloor\frac{n}{(T+1)^2}\right\rfloor

总复杂度分三块。线性筛 $O(T)$ ，直接枚举 $O(T)$ 。分块部分：所有会被查询的 $M$ 的参数都形如 $\lfloor\sqrt{n/m}\rfloor$ ，只有 $m<Q=n^{1/5}$ 个不同的值大于 $T$ （更小的直接查表），而对参数 $x$ 做一次杜教筛的整除去分块需要 $O(\sqrt x)$ 次迭代，于是分块部分的开销是

\sum_{m=1}^{Q}O\!\left(n^{1/4}m^{-1/4}\right)=O\!\left(n^{1/4}Q^{3/4}\right)=O\!\left(n^{1/4}\cdot n^{3/20}\right)=O\!\left(n^{2/5}\right)

取 $T=n^{2/5}$ 时三块同为 $O(n^{2/5})$ ；若把 $T$ 调大，分块变便宜但线性筛变贵， $n^{2/5}$ 正是两侧的平衡点（ $T$ 与 $n\cdot T^{-3/2}$ 相等）。

以 $n=1000$ （ $\sqrt n\approx31$ ）为例，取 $T=20$ ，两段分别长这样：

分段	$q$	$d$ 的范围	项数	$\sum\mu(d)$	贡献
直接枚举	—	$1\leqslant d\leqslant20$	$20$	—	$607$
分块	$1$	$23\leqslant d\leqslant31$	$9$	$-3$	$-3$
分块	$2$	$21\leqslant d\leqslant22$	$2$	$2$	$4$

三段相加得到 $607-3+4=608$ ，与暴力枚举 $d\leqslant\sqrt n$ 的结果一致。注意第二行 $q=1$ 的段原本算出的下界是 $d>22$ ，已经大于 $T=20$ ，而第三行 $q=2$ 的原始下界是 $18<20$ ，必须把它抬到 $T$ 才能保证 $d>T$ 、不和第一段重复统计。这一步是本题实现里最容易写错的地方。

思路

取 $T=\min\big(\lfloor\sqrt n\rfloor,\ \lfloor n^{2/5}\rfloor\big)$ ，并用数组容量兜住上界（本实现上限 $1.2\times10^7$ ，对应 $n=10^{18}$ 时的 $T\approx1.2\times10^7$ ）。
线性筛出 $\mu(1..T)$ ，在累加第一段之前先直接用 $\mu$ 累加 $d\leqslant T$ 的贡献，然后把数组原地改造成前缀和 $M$ ，供杜教筛查表使用。
算出块数 $Q=\lfloor n/(T+1)^2\rfloor$ ，对 $q=1..Q$ 分块累加；每段的下界 $\lfloor\sqrt{n/(q+1)}\rfloor$ 若小于 $T$ 就抬到 $T$ 。
杜教筛内部用 __int128 累加： $(last-d+1)\cdot M(v)$ 中 $M(v)$ 的绝对值可达 $10^9$ 量级，两者相乘会超出 int，虽然 $M(x)$ 本身一定落在 long long 内，中间乘积仍需更宽的中间类型才稳妥。

求 $\lfloor\sqrt x\rfloor$ 时用 sqrtl 估一个初值，再用整数乘法微调，避免 $x$ 接近 $10^{18}$ 时 long double 舍入导致结果差一。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:07
 * update_at: 2026-10-02 15:07
 */
/*
 * P9238 [蓝桥杯 2023 省 A] 翻转硬币
 *
 * 结论：最少操作次数 = 1..n 中「无平方因子数」的个数。
 *
 * 记 x_i 表示是否使用一次操作 i（同一个操作用两次等于没用，所以 x_i 只有 0/1）。
 * 硬币 j 最终被翻转的次数是 sum_{i | j} x_i，要求全部朝上：
 *   j = 1 : x_1 = 1
 *   j >= 2: sum_{i | j} x_i = 0 (mod 2)
 * 按 j 从小到大看，第 j 个方程里只出现 x_i (i | j 且 i <= j)，且 x_j 的系数为 1，
 * 于是每个 x_j 都被唯一确定，解正是 x = mu（莫比乌斯函数）。
 * 所以答案 = sum_{i = 1}^{n} [mu(i) != 0] = n 以内无平方因子数的个数。
 *
 * 用容斥（按最小平方因子枚举所有平方数）得到
 *   Q(n) = sum_{d = 1}^{floor(sqrt(n))} mu(d) * floor(n / d^2)。
 * sqrt(n) 最大 1e9，不能直接枚举，于是分成两段：
 *   1) d <= T：线性筛出 mu，直接累加；
 *   2) d >  T：按 q = floor(n / d^2) 分块。q 相同的一段可以批量算，
 *      段内的莫比乌斯和用杜教筛求前缀和 M = sum mu。
 * 取 T = floor(n^(2/5))（并限制在数组容量内），此时块数 Q = floor(n / (T+1)^2)
 * 只有 n^(1/5) 量级，整体复杂度 O(n^(2/5))，n = 1e18 时 0.4s 左右。
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXT = 12000000;      // 阈值上限，约 52MB 内存
static int mu[MAXT + 5];        // 先存 mu(i)，需要时再原地改造成前缀和 M(i)
static int primes[800000];      // 素数表
static unsigned long long notprime[(MAXT >> 6) + 5]; // 合数标记位图
int pcnt;                       // 素数个数
ll T;                           // 直接计算的阈值
unordered_map<ll, ll> memo;     // 杜教筛的记忆化

// 求 floor(sqrt(x))：用 long double 估一个初值，再靠整数运算微调，避免精度问题
ll isqrt_ll(ll x) {
    if (x <= 0) return 0;
    ll r = (ll)sqrtl((long double)x);
    while ((r + 1) <= x / (r + 1)) r++;
    while (r > x / r) r--;
    return r;
}

// 杜教筛：莫比乌斯前缀和 M(x) = sum_{i = 1}^{x} mu(i)
// 由 mu * 1 = eps 得 1 = sum_{d = 1}^{x} M(floor(x / d))，
// 移项就有 M(x) = 1 - sum_{d = 2}^{x} M(floor(x / d))，对 d 整除分块即可
ll mertens(ll x) {
    if (x <= T) return mu[x];               // 小范围查表
    unordered_map<ll, ll>::iterator it = memo.find(x);
    if (it != memo.end()) return it->second;
    __int128 res = 1;                       // sum_{i = 1}^{x} eps(i) = 1
    for (ll d = 2; d <= x; ) {
        ll v = x / d;                       // 这一段的 floor(x / d) 都等于 v
        ll last = x / v;
        res -= (__int128)(last - d + 1) * mertens(v);
        d = last + 1;
    }
    ll rr = (ll)res;                        // M(x) 的绝对值不超过 x，一定放得下
    memo[x] = rr;
    return rr;
}

int main() {
    ll n;
    scanf("%lld", &n);

    // 阈值 T = min(floor(sqrt(n)), floor(n^(2/5)))，并保证不越界
    T = isqrt_ll(n);
    ll t = (ll)powl((long double)n, 0.4L) + 5;
    if (t < T) T = t;
    if (T > MAXT) T = MAXT;
    if (T < 1) T = 1;
    int N = (int)T;

    // 线性筛莫比乌斯函数，此时 mu[i] 就是 mu(i)
    mu[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!((notprime[i >> 6] >> (i & 63)) & 1ULL)) {
            primes[++pcnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= pcnt; j++) {
            ll v = (ll)primes[j] * i;
            if (v > N) break;
            notprime[v >> 6] |= 1ULL << (v & 63);
            if (i % primes[j] == 0) {
                mu[v] = 0;                  // v 含平方因子
                break;
            }
            mu[v] = -mu[i];
        }
    }

    // 第一段：d <= T 的部分直接累加 mu(d) * floor(n / d^2)
    ll ans = 0;
    for (ll d = 1; d <= T; d++) {
        ans += (ll)mu[d] * (n / (d * d));
    }

    // 把 mu 原地改造成前缀和 M(i)，供杜教筛查表
    for (int i = 1; i <= N; i++) mu[i] += mu[i - 1];

    // 第二段：d > T。此时 floor(n / d^2) = q <= Q，按 q 分块批量算
    ll Q = n / ((T + 1) * (T + 1));
    for (ll q = 1; q <= Q; q++) {
        ll hi = isqrt_ll(n / q);            // floor(n / d^2) >= q 的最大 d
        ll lo = isqrt_ll(n / (q + 1));      // floor(n / d^2) >= q+1 的最大 d
        if (lo < T) lo = T;                 // 只统计 d > T，避免和第一段重复
        // d 在 (lo, hi] 内时 floor(n / d^2) 恰好等于 q，
        // 这些 d 的 mu 之和是 M(hi) - M(lo)，乘上系数 q 累加
        ans += q * (mertens(hi) - mertens(lo));
    }

    printf("%lld\n", ans);
    return 0;
}

复杂度

时间复杂度： $O(n^{2/5})$ 。 $n=10^{18}$ 时 $T\approx1.2\times10^7$ 、 $Q=6944$ ，实测约 $0.33$ s（其中线性筛 $0.03$ s、直接枚举 $0.01$ s、分块累计 $0.29$ s）。分块部分内部循环约 $6.4\times10^7$ 次，与 $n^{2/5}$ 同量级，而直接枚举所有 $d$ 需要 $10^9$ 次。
空间复杂度： $O(n^{2/5})$ ，主要是 $\mu$ 数组（int）、合数位图与素数表，实测峰值约 $52$ MB。

正确性上， $d\leqslant T$ 与 $d>T$ 两段的并集恰好是 $1\leqslant d\leqslant\lfloor\sqrt n\rfloor$ 且不重叠（靠把下界抬到 $T$ 保证），每一段内部按定义等于 $\mu(d)\lfloor n/d^2\rfloor$ 求和，故答案与容斥公式完全一致。

总结

本题的难点不在实现，而在两步「翻译」：

把「最少操作次数」翻译成唯一解。同一操作做两次相互抵消，每个 $x_i$ 只取 $0/1$ ；按 $j$ 递增看，第 $j$ 个同余方程里 $x_j$ 系数为 $1$ ，于是解唯一，最小值不需要搜索。这个唯一解恰好是莫比乌斯函数，答案就是 $n$ 以内的无平方因子数个数。想清楚这一点，题目就从一道操作题变成了一道数论计数题。
把「数出 $n$ 以内的无平方因子数」翻译成可以分块的求和。容斥给出一重和 $Q(n)=\sum_{d\leqslant\sqrt n}\mu(d)\lfloor n/d^2\rfloor$ ；瓶颈是 $\sqrt n$ 太大，而 $\lfloor n/d^2\rfloor$ 的取值很少，于是对 $q$ 分块（块数 $n^{1/5}$ ），段内用杜教筛求莫比乌斯前缀和（ $O(x^{2/3})$ ，整除分块 + 记忆化）。取阈值 $T=n^{2/5}$ 平衡线性筛的 $O(T)$ 与分块部分的 $O(n\,T^{-3/2})$ ，总复杂度 $O(n^{2/5})$ 。

三层的递进关系也值得记住：暴力解法按定义统计无平方因子数，是把「答案 = 无平方因子数个数」这个结论落到代码上最直接的写法（ $n=7$ 输出 $6$ 、 $n=1131796$ 输出 $688042$ ，与题面两个样例一致）；子任务解法把「按数遍历」换成「按 $d$ 遍历」；正解再把「按 $d$ 遍历」换成「按取值分块」。每一步都只移除上一层暴露出来的那一个瓶颈。