C语言程序设计100例之（17）：百灯判亮
例17 百灯判亮
问题描述
有序号为1、2、3、…、99、100的100盏灯从左至右排成一横行，且每盏灯各由一个拉线开关控制着，最初它们全呈关闭状态。有100个小朋友，第1位走过来把凡是序号为1的倍数的电灯开关拉一下；接着第2位小朋友走过来，把凡是序号为2的倍数的电灯开关拉一下；第3位小朋友走过来，把凡是序号为3的倍数的电灯开关拉一下；如此下去，直到第100个小朋友把序号为100的电灯开关拉一下。问这样做过一遍之后，哪些序号的电灯是亮着的？
输入格式
每行测试数据是一个正整数n，代表第n盏灯。
输出格式
每行输出第n盏灯的状态，0代表灯是熄灭的，1代表灯是亮的。
输入样例
1
5
输出样例
1
0
（1）编程思路1。
要判定哪些序号的灯是亮的，需要知道100个小朋友操作过后，每盏灯的拉线开关被拉的次数，这样凡是被拉了奇数次开关的灯最后就是亮的。
为了保存每盏灯的拉线开关被拉的次数，需要定义一个一维数组int a[101]；用数组元素a[1]~a[100]保存1~100号灯的开关被拉的次数（初始值为0，表示开关没有被拉1次）。
程序用一个二重循环来模拟小朋友的操作过程。外循环控制小朋友从1~100，对于第i个小朋友，他拉第i、2i、3i…号灯的拉线开关的操作构成内循环。具体描述为：
for (child=1;child<=100;child++) // 小朋友从1~100
for (lamp=child;lamp<=100;lamp+=child) // 第i个小朋友从第i号灯开始操作
a[lamp]++;
经过循环模拟小朋友拉开关的动作后，判定元素a[i]的奇偶性，如果a[i]为奇数，则第i盏灯是亮的。
（2）源程序1。
#include <stdio.h>
int main()
{
int a[101],child,lamp; // a[1]~a[100]保存1~100盏灯的开关被拉的次数
for (lamp=0;lamp<=100;lamp++)
a[lamp]=0;
for (child=1;child<=100;child++)
for (lamp=child;lamp<=100;lamp+=child)
a[lamp]++;
int n;
while (scanf("%d",&n)!=eof)
{
if (a[n]%2)
printf("1\n");
else
printf("0\n");
}
return 0;
}
（3）编程思路2。
实际上，除了采用思路1的方式用数组直接模拟外，本例还可以这样做。
我们知道，第n盏灯的拉线开关只会由编号为其约数的小朋友拉一下。例如，第24盏灯，会由编号分别为1、2、3、4、6、8、12、24的小朋友拉一下，它被拉了偶数次，故它最终是熄灭的。
更一般地，对于第n盏灯，若n=i*j，则一定有编号为i的小朋友的操作将灯由0变成1，编号为j的小朋友的操作会将灯由1变成0。最后，当且仅当n=i*i时，灯是亮的。
因此，本题实质是判断n是否是完全平方数即可。
（4）源程序2。
#include <stdio.h>
#include <math.h>
int main()
{
int n,k;
while (scanf("%d",&n)!=eof)
{
k=(int)sqrt(1.0*n);
if (k*k==n)
printf("1\n");
else
printf("0\n");
}
return 0;
}
习题17
17-1 the drunk jailer
本题选自北大poj题库（http://poj.org/problem?id=1218）
description
a certain * contains a long hall of n cells, each right next to each other. each cell has a *er in it, and each cell is locked.
one night, the jailer gets bored and decides to play a game. for round 1 of the game, he takes a drink of whiskey,and then runs down the hall unlocking each cell. for round 2, he takes a drink of whiskey, and then runs down the
hall locking every other cell (cells 2, 4, 6, ?). for round 3, he takes a drink of whiskey, and then runs down the hall. he visits every third cell (cells 3, 6, 9, ?). if the cell is locked, he unlocks it; if it is unlocked, he locks it. he
repeats this for n rounds, takes a final drink, and passes out.
some number of *ers, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. they immediately escape.
given the number of cells, determine how many *ers escape jail.
input
the first line of input contains a single positive integer. this is the number of lines that follow. each of the following lines contains a single integer between 5 and 100, inclusive, which is the number of cells n.
output
for each line, you must print out the number of *ers that escape when the * has n cells.
sample input
2
5
100
sample output
2
10
（1）编程思路。
本题与例17本质上是同类型的题，只是最终输出不一样。按例17的两种思路可以编写源程序1和2如下。
（2）源程序1。
#include <stdio.h>
int main()
{
int t,n,i,j,cnt,a[101]={0};
scanf("%d",&t);
for (i=1;i<=100;i++)
for (j=i;j<=100;j+=i)
a[j]=1-a[j];
while (t--)
{
scanf("%d",&n);
cnt=0;
for (i=1;i<=n;i++)
if (a[i]==1) cnt++;
printf("%d\n",cnt);
}
return 0;
}
（3）源程序2。
#include <stdio.h>
#include <math.h>
int main()
{
int t,n;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
printf("%d\n",(int)sqrt(1.0*n));
}
return 0;
}
17-2 开灯
本题选自洛谷题库 （https://www.luogu.org/problem/p1876）
题目描述
首先所有的灯都是关的（注意是关！），编号为1的人走过来，把是1的倍数的灯全部打开；编号为2的人把是2的倍数的灯全部关上；编号为3的人又把是3的倍数的灯开的关上，关的开起来……直到第n个人为止。
给定n，求n轮之后，还有哪几盏是开着的。
输入格式
一个数n（1<=n<=2^40），表示灯的个数和操作的轮数。
输出格式
若干数，表示开着的电灯编号
输入样例
5
输出样例
1 4
（1）编程思路。
本题中n的值可能很大，因此采用例1中的思路1用数组模拟肯定会超时，因此只能采用思路2的做法。通过判断正整数i（1<=i<=n）是否为完全平方数，决定编号为i的灯是否是开着的。
（2）源程序。
#include <stdio.h>
int main()
{
long int i,n;
scanf("%ld",&n);
for (i=1;i*i<=n;i++)
printf("%ld ",i*i);
return 0;
}
17-3 又是开灯
本题选自洛谷题库 （https://www.luogu.org/problem/p1161）
题目描述
在一条无限长的路上，有一排无限长的路灯，编号为1,2,3,4,…。
每一盏灯只有两种可能的状态，开或者关。如果按一下某一盏灯的开关，那么这盏灯的状态将发生改变。如果原来是开，将变成关。如果原来是关，将变成开。
在刚开始的时候，所有的灯都是关的。小明每次可以进行如下的操作：
指定两个数，a,t（a为实数，t为正整数）。将编号为[a],[2×a],[3×a],…,[t×a]的灯的开关各按一次。其中[k]表示实数k的整数部分。
在小明进行了n次操作后，小明突然发现，这个时候只有一盏灯是开的，小明很想知道这盏灯的编号，可是这盏灯离小明太远了，小明看不清编号是多少。
幸好，小明还记得之前的n次操作。于是小明找到了你，你能帮他计算出这盏开着的灯的编号吗？
输入格式
第一行一个正整数n，表示n次操作。
接下来有n行，每行两个数a,t，其中a 是实数，小数点后一定有6位，t是正整数。
输出格式
仅一个正整数，那盏开着的灯的编号。
输入样例
3
1.618034 13
2.618034 7
1.000000 21
输出样例
20
说明/提示
数据保证，在经过n次操作后，有且只有一盏灯是开的，不必判错。
（1）编程思路。
本题如果采用例17的思路1进行模拟不是一种恰当的解法。首先题目中没有说明数据范围，只说“在一条无限长的路上，有一排无限长的路灯”，因此定义数组元素的个数需要斟酌；另外，n次操作，每次操作若干盏灯，模拟下来也可能会超时。因此，需要想出其他更简便的解决方法。
注意到题目的提示“在经过n次操作后，有且只有一盏灯是开的”。也就是说n次操作中除了一盏灯被按的次数是奇数次外，其余编号的灯被按的次数一定是偶数次。
以样例给出的数据为例：
第1次，“1.618034 13”，编号为1,3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21这13盏灯的开关会被按一下；
第2次，“2.618034 7”，编号为2，5，7，10，13，15，18这7盏灯的开关会被按一下；
第3次，“1.000000 21”，编号为1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20，21这21盏灯的开关会被按一下。
可以看出除了编号20的灯外，其余编号均出现偶数次，即两两会成对出现。
异或运算有一个特性：数x与自身异或其值一定为0，而0和x异或结果为x。因此，将上面的表示灯的编号的41个数全部异或起来，结果一定是答案。因为根据题目的提示“在经过n次操作后，有且只有一盏灯是开的”可知，除一盏灯外，其余灯的编号一定两两出现，异或后一定为0。
（2）源程序。
#include <stdio.h>
int main()
{
int n,t,i,ans;
double a;
scanf("%d",&n);
ans=0;
while (n--)
{
scanf("%lf%d",&a,&t);
for (i=1;i<=t;i++)
ans=ans^((int)(a*i));
}
printf("%d\n",ans);
return 0;
}