说明

这道题目描述了一个监狱走廊中有 𝑛 间牢房，初始时所有牢房都是锁着的。狱警进行 𝑛 轮操作，每轮操作会切换特定牢房的状态（开锁或上锁）。最终，我们需要计算有多少间牢房是开着的，即有多少囚犯可以成功越狱。

算法标签

• 数论
• 数学推导

解题思路

1. 问题分析：狱警的每一轮操作实际上是对牢房状态的切换。第 𝑖 轮操作会切换所有 𝑖 的倍数的牢房的状态（例如，第1轮切换所有牢房，第2轮切换第2、4、6...间牢房，依此类推）。
2. 关键观察：一个牢房最终的状态取决于它被切换的次数。如果牢房的编号有偶数个因数，它最终会被锁上；如果有奇数个因数，它最终会被打开。
3. 数学推导：只有完全平方数的因数个数是奇数（因为因数是成对出现的，完全平方数的平方根会与自己配对）。因此，最终打开的牢房编号都是完全平方数。
4. 结论：对于给定的 𝑛，答案就是不超过 𝑛 的完全平方数的个数，即 ⌊√𝑛⌋。

分析

• 牢房状态切换：每个牢房在第 𝑖 轮被切换当且仅当 𝑖 能整除该牢房的编号。因此，牢房 𝑘 被切换的次数等于 𝑘 的因数个数。
• 完全平方数性质：非完全平方数的因数个数是偶数（因数是成对出现的），而完全平方数的因数个数是奇数（因为其中一个因数是其平方根，只算一次）。
• 结果推导：最终打开的牢房编号是1, 4, 9, 16, ..., 𝑘²（其中 𝑘² ≤ 𝑛）。因此，打开的牢房数量就是 ⌊√𝑛⌋。

实现步骤

1. 输入处理：读取测试用例的数量 𝑡。
2. 循环处理每个测试用例：
   • 读取牢房数量 𝑛。
   • 计算 ⌊√𝑛⌋，即不超过 𝑛 的最大整数平方根。
   • 输出结果。
3. 输出结果：对于每个测试用例，输出 ⌊√𝑛⌋。

代码

/* POJ1218 ZOJ1350 HDU1337 UVALive2557 THE DRUNK JAILER */
 
#include <stdio.h>
#include <math.h>
 
int main(void)
{
    int t, n;
 
    scanf("%d",&t);
    while(t--) {
        scanf("%d", &n);
 
        printf("%d\n", (int)sqrt(n));
    }
 
    return 0;
}