灯泡开关问题 详细题解

问题核心转化

有编号为 $1,2,3,\dots$ 的无限个灯泡，初始状态均为关闭。 第 $1$ 轮：切换所有 $1$ 的倍数的灯泡； 第 $2$ 轮：切换所有 $2$ 的倍数的灯泡； 第 $i$ 轮：切换所有 $i$ 的倍数的灯泡； 无限轮操作后，求第 $k$ 个亮着的灯泡的编号。

一、数学推导：灯泡最终状态规律

1. 灯泡状态与约数个数的关系

灯泡 $i$ 被切换的次数 = $i$ 的正约数的个数。

• 初始状态：关闭
• 切换偶数次：最终亮
• 切换奇数次：最终灭

因此：

• 若 $i$ 有偶数个约数 $\rightarrow$ 灯泡亮
• 若 $i$ 有奇数个约数 $\rightarrow$ 灯泡灭

2. 约数个数的奇偶性规律

正整数的约数都是成对出现的（如 $6$ 的约数：$1\times6,2\times3$），因此绝大多数数的约数个数为偶数。 只有完全平方数（$1,4,9,16,\dots$）存在一个约数是自身平方根（如 $4=2\times2$），约数会重复，最终约数个数为奇数。

结论：

• 非完全平方数 $\rightarrow$ 灯泡亮
• 完全平方数 $\rightarrow$ 灯泡灭

问题简化为：求第 $k$ 个非完全平方数。

二、核心公式推导

设目标数为 $n$，在 $1\sim n$ 中：

• 完全平方数的个数为 $\lfloor \sqrt{n} \rfloor$（向下取整）
• 非完全平方数的个数为 $n - \lfloor \sqrt{n} \rfloor$

我们需要找到最小的 $n$，满足：

1. 二分查找解法（标程思路）

二分查找的核心：在范围 $[1, 2\times10^{18}]$ 内寻找满足 $n - \lfloor \sqrt{n} \rfloor \geq k$ 的最小 $n$。

• 左边界 $l=1$，右边界 $r=2\times10^{18}$（覆盖极大数据范围）
• 取中间值 $mid$，计算 $1\sim mid$ 内非完全平方数的个数 $mid - \lfloor \sqrt{mid} \rfloor$
• 若个数 $\geq k$，说明答案在左半区间，调整右边界；否则调整左边界
• 最终 $r$ 即为第 $k$ 个非完全平方数

2. 直接公式解法

数学推导可得直接计算公式：

该公式可直接计算出答案，效率更高。

三、标程代码解析

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin >> t;        // 输入测试用例数
    while(t--){      // 循环处理每个测试用例
        long long k, l = 1, r = 2e18;
        cin >> k;    // 输入目标k
        // 二分查找核心逻辑
        while(r - l > 1){
            long long mid = (l + r) >> 1;  // 等价于 (l+r)/2，避免溢出
            // 计算1~mid中非完全平方数的个数，sqrtl为高精度平方根函数
            long long cnt = mid - (long long)sqrtl(mid);
            if(cnt >= k) r = mid;  // 个数足够，答案在左区间
            else l = mid;          // 个数不足，答案在右区间
        }
        cout << r << "\n";  // 输出最终答案
    }
    return 0;
}

关键细节说明

1. 数据类型：使用 long long 避免数据溢出（$k$ 可极大）
2. 高精度平方根：sqrtl() 用于长整型的平方根计算，保证精度
3. 二分边界：右边界设为 $2\times10^{18}$，覆盖所有题目可能的输入范围
4. 循环条件：r-l>1 确保最终找到唯一解 $r$

四、示例验证

• 当 $k=1$：第 $1$ 个非完全平方数是 $2$，公式：$\lfloor 1+\sqrt{1}+0.5 \rfloor=2$
• 当 $k=3$：第 $3$ 个非完全平方数是 $5$，公式：$\lfloor 3+\sqrt{3}+0.5 \rfloor=5$
• 当 $k=5$：第 $5$ 个非完全平方数是 $7$，公式：$\lfloor 5+\sqrt{5}+0.5 \rfloor=7$

验证结果完全正确。

总结

1. 灯泡亮灭等价于判断是否为非完全平方数；
2. 问题转化为求第 $k$ 个非完全平方数；
3. 核心公式：$\boldsymbol{n - \lfloor \sqrt{n} \rfloor = k}$；
4. 解法：二分查找（标程）/ 直接公式 $\boldsymbol{n = \lfloor k + \sqrt{k} + 0.5 \rfloor}$。