例17 百燈判亮 問題描述 有序號為1、2、3、…、99、100的100盞燈從左至右排成一橫行，且每盞燈各由一個拉線開關控制著，最初它們全呈關閉狀態。有100個小朋友，第1位走過來把凡是序號為1的倍數的電燈開關拉一下；接著第2位小朋友走過來，把凡是序號為2的倍數的電燈開關拉一下；第3位小朋友走過來， ...
例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 prison contains a long hall of n cells, each right next to each other. Each cell has a prisoner 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 prisoners, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. They immediately escape.
Given the number of cells, determine how many prisoners 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 prisoners that escape when the prison 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;
}
