POJ1218 THE DRUNK JAILER

问题链接：POJ1218 THE DRUNK JAILER。

题意简述：输入n，n为5-100间的一个数，代表有多少间牢房。刚开始所有房间打开，第1轮2的倍数的房间门翻转（打开的关上，关上的打开），第2轮3的倍数，第3轮4的倍数，......，第n-1轮n的倍数。求最后有几间牢房门是打开的。

问题分析：使用模拟法，模拟这个过程即可。好在计算规模不算大。

AC的C语言程序如下：

/* POJ1218 THE DRUNK JAILER */

#include <stdio.h>
#include <memory.h>

#define MAXN 100

int cell[MAXN+1];

int main(void)
{
    int t, n, sum, i, j;

    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);

        memset(cell, 0, sizeof(cell));

        for(i=2; i<=n; i++)
            for(j=i; j<=n; j++)
                if (j%i == 0)
                    cell[j] = 1 - cell[j];

        sum = 0;
        for(i=1; i<=n; i++)
            if(cell[i] == 0)
                sum++;

        printf("%d\n",sum);
    }

    return 0;
}

还有一种大牛做的，直接计算的方法，其数学道理真的不懂。AC的C语言程序如下：

/* POJ1218 THE DRUNK JAILER */

#include <stdio.h>
#include <math.h>

int main(void)
{
    int t, n, ans;

    scanf("%d",&t);
    while(t--) {
        scanf("%d", &n);

        ans = (int)sqrt(n);

        printf("%d\n", ans);
    }

    return 0;
}

POJ1218 THE DRUNK JAILER

原文：http://blog.csdn.net/tigerisland45/article/details/52199831