poj 1218 THE DRUNK JAILER

/*

 * http://sosal.tistory.com/
 * made by so_Sal
 */

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

Source

Greater New York 2002

문제를 보고 정말 단순하게 프로그래밍 했습니다.

말 그대로 간수가 술취해가지곤 감옥을 열었다 닫았다 하는데

100개의 감옥이 쭉~ 존재한다면

1부터 100이라는 숫자까지 등차수열로 문을 열고 닫는데,

마지막으로 열려있는 감옥 (즉 도망간 죄수)의 수를 구하는것이 문제입니다.

- ex)

숫자 4가 주어진다면 감옥이 4개 존재.

1: 1의 배열에 해당되는 모든 감옥의 문을 열어라. (열려있으면 닫아라.)

2: 2의 배열에 해당되는 모든 감옥의 문을 열어라. (열려있으면 닫아라.)

3: 3의 배열에 해당되는 모든 감옥의 문을 열어라. (열려있으면 닫아라.)

4: 4의 배열에 해당되는 모든 감옥의 문을 열어라. (열려있으면 닫아라.)

이렇게 4번의 수행을 한 후에

열려있는 감옥의 수를 출력하는것이 문제입니다.

처음 문제를 풀땐 정말 단순하게 문제에서 주어진대로 프로그래밍 하였습니다.

#include<iostream>

#include<string>

#include<algorithm>

#include<vector>

using namespace std;

int main(){

while(1){

bool cell[101]={0,};

int N;

cin>>N;

for(int i=1;i<=N;i++){

for(int j=i; j<=N; j+=i){

if(cell[j] == 0)

cell[j] =1 1;

else

cell[j] = 0;

}

}

int count = 0;

for(int i=1;i<=N;i++){

if(cell[i] == 1)

count++;

}

cout<<count<<endl;

}

}

하지만 이 문제의 본질을 살펴보시면

1부터 N까지를 공차로 하는 등차수열을 짜는것인데,

이는 결국 각 수의 약수 개수만큼 열었다 닫았다 하는 원리입니다.

1과 제곱근을 가지는 수(자연수)를 제외한 모든 수는 약수를 짝수로 가지게 됩니다.

참조: http://www.imaeil.com/sub_news/sub_news_view.php?news_id=33528&yy=2007

따라서 N개의 감옥이 존재할 때, 결론적으로 문이 열리는 감옥의 갯수는

N보다 작거나 같은 모든 자연수중에 제곱근의 갯수 (1포함)과 똑같이 됩니다.

그것은 (int) sqrt(N) 의 갯수와 똑같겠죠?

그래서 다음과 같이 문제를 해결할 수 있습니다.

int main(){

int N;

cin>>N;

int in;

while(N--){

cin>>in;

cout<<(int)sqrt((double)in)<<endl;

}

}