版权声明：本文为博主原创文章，未经博主同意不得转载。 https://blog.csdn.net/sr19930829/article/details/37727417
THE DRUNK JAILER
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 23246 | Accepted: 14641 |
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, ?
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
解题思路：
题意为n个*,编号1到n，初始均关闭，进行n局游戏，第一局，把全部的*都打开，第i(i>=2)局，把编号为 i 的倍数的*的状态改变（打开变为关闭或关闭变为打开）。问n局游戏以后，有多少个*为打开状态。 用d[]数组来保存*的状态。模拟n局游戏就能够了。
代码：
#include <iostream>
#include <string.h>
#include <stack>
#include <iomanip>
#include <cmath>
using namespace std;
bool d[110];
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
int cnt=0;
memset(d,0,sizeof(d));
for(int i=2;i<=n;i++)
{
for(int j=i;j<=n;j+=i)
d[j]=1-d[j];//状态改变
}
for(int i=1;i<=n;i++)
if(d[i]==0)
cnt++;
cout<<cnt<<endl;
}
return 0;
}