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
Source: Greater New York
2002
脑子比较笨用的是最北的遍历方法。代码如下：
#include <stdio.h>
#include <string.h> int cell[];//0表示牢房锁闭，1为打开状态 int main ()
{
int n;
scanf("%d",&n); int num;
int unlockCount; int i,j; while(n--)
{
unlockCount=;
memset(cell,,*sizeof(int)); scanf("%d",&num);
for(i=;i<=num;i++)
{
for(j=i;j<=num;j+=i)
{
if(cell[j] == )
cell[j]=;
else
cell[j]=;
}
}
for(i=;i<=num;i++)
if(cell[i] == )
unlockCount++;
printf("%d\n",unlockCount);
}
return ;
}
看到网上还有许多其他解法，一并参考下：
1、转载自：http://blog.csdn.net/sinchb/article/details/8075949
最笨的方法，就是列一个长度为n的数组代表cell是locked还是unlocked，然后按照游戏方法，遍历n次该数组，不断改变数组中的值，这样时间复杂度是O(n*n)。但是经过观察发现，一个cell被开关的次数其实是有规律的，也就是这个cell的编号n的约数的数量；比如4，他的约数有1,2,4，所以编号为4的cell会在游戏的第1,2,4轮被开/关。又如果一个cell被开/关的最终次数为偶数次，则该cell最终也就是关闭的，这个cell里可怜的*er将无法上演《越狱》，只有cell编号的约数数量为奇数的，才有机会逃跑。所以，问题转换为，求一个数1~n中，有多少数有奇数个约数。
#include <stdio.h>
int main()
{
short unsigned cell[] = {,,,,,},i = ,j,top,sum = ;
int N,n;
for(i = ;i <= ;i++)
{
sum = ;
top = i>>;
for(j = ;j <= top ;j++)
!(i % j) ? sum++ :;
cell[i] = cell[i-] + sum%;
}
scanf("%d",&N);
while(N--)
{
scanf("%d",&n);
printf("%d\n",cell[n]);
}
return ;
}
2、转载自：http://zhidao.baidu.com/link?url=4SkSUEHqhMhNniqchgFztGMNMemf8zP-UgP_ZTVE4TqAqfIGYF-UM8z4m_wHaoOhJLC-ILQUGk5ofRY2GfNEEK
代码比较简洁 编号为1的门只为1的倍数，所以只执行了一次操作，所以其最后的状态是开，编号为2的门只为1和2的倍数，执行了两次操作，其最后的状态是关，编号为3的门为1和3的倍数，执行了三次操作，其最后的状态为关，编号为4的门为1、2、4的倍数，执行了三次操作，其最后的状态为开......以此类推，如果编号为一个数的平方数，则其执行操作的次数为奇数次，其最后的状态为开。于是只要求出小于这个数的正整数中有几个数是平方数即可。
#include<stdio.h>
#include<math.h>
int main(void){int n, a, on;
scanf("%d",&n);
while(n--){
scanf("%d",&a);
on=(int)sqrt(a);
printf("%d\n",on);
}
return0;
}