「NordicOI 2017」Yule Lads 题解

问题分析

我们有 $N$ 座房子和 $N$ 个小矮人。第 $K$ 个小矮人会切换所有编号为 $K$ 的倍数的房子的灯状态。最终状态是：只有第 $1$ 座房子灯是关的，其他所有房子灯都是亮的。

我们需要找出实际来过的小矮人数量。

数学模型

关键观察

设 $f(k)$ 表示第 $k$ 个小矮人是否来过（1表示来过，0表示没来）。

对于房子 $i$，它的最终状态由所有 $k \mid i$ 的小矮人决定：

$$\text{final}[i] = \left(\sum_{k \mid i} f(k)\right) \bmod 2 $$

题目要求：

• $\text{final}[1] = 1$（第1座房子灯关）
• $\text{final}[i] = 0$ 对于所有 $i > 1$（其他房子灯亮）

这实际上是一个莫比乌斯反演问题。定义：

$$F(n) = \sum_{d \mid n} f(d)$$

已知：

• $F(1) = 1$
• $F(n) = 0$ 对于 $n > 1$

由莫比乌斯反演：

$$f(n) = \sum_{d \mid n} \mu(d) F\left(\frac{n}{d}\right) $$

代入已知的 $F$ 值：

$$f(n) = \mu(1) F(n) + \sum_{\substack{d \mid n \\ d > 1}} \mu(d) F\left(\frac{n}{d}\right) = \mu(n) $$

因此，$f(n) = \mu(n)$。

但是我们需要的是 $f(n) = 1$ 的数量，即 $\mu(n) = 1$ 的数量。

最终答案

来过的小矮人数量 = 满足 $\mu(n) \neq 0$ 且 $n \leq N$ 的 $n$ 的数量。

即：所有无平方因子的数的个数。

---

代码实现

1. 计算范围确定

ll n;
cin >> n;

ll to = 1;
while (to*to <= n) to++;  // 计算 sqrt(n)

2. 线性筛法计算莫比乌斯函数

int *mob = new int[to+1];
bool *prime = new bool[to+1];
rep(i,0,to+1) {
    mob[i] = 1;
    prime[i] = true;
}

for (int i = 2; i <= to; i++) {
    if (prime[i]) {
        for (int j = i; j <= to; j += i) {
            prime[j] = false;
            mob[j] = -mob[j];        // 第一次遇到质因子
            if ((j/i)%i == 0) {
                mob[j] = 0;          // 有平方因子
            }
        }
    }
}

算法原理：

• mob[i] 存储 $\mu(i)$
• 遇到质数时，将其倍数乘以 $-1$
• 如果发现平方因子，设为 $0$

3. 统计无平方因子数个数

ll cnt = 0;
for (ll i = 1; i*i <= n; i++) {
    cnt += mob[i] * (n / i / i);
}
cout << cnt << endl;

数学原理：

$$\text{答案} = \sum_{i=1}^{\lfloor\sqrt{n}\rfloor} \mu(i) \left\lfloor \frac{n}{i^2} \right\rfloor $$

这个公式计算了 $1$ 到 $n$ 中无平方因子数的个数。

复杂度分析

• 时间复杂度：$O(\sqrt{N})$，线性筛到 $\sqrt{N}$
• 空间复杂度：$O(\sqrt{N})$，存储莫比乌斯函数数组

算法优势

$1.$ 数学优化：利用莫比乌斯函数的性质，将问题转化为经典数论问题

$2.$ 高效计算：使用线性筛法，避免暴力枚举

$3.$ 可扩展性：能够处理 $N \leq 10^{13}$ 的大数据范围

该解法通过深入的数学分析和高效的算法实现，完美解决了这个看似复杂的灯开关问题。