开灯问题 —— POJ 1218 THE DRUNK JAILER

本文主要是介绍开灯问题 —— POJ 1218 THE DRUNK JAILER，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对应POJ 题目：点击打开链接

Description

Input

Output

Sample Input

2
5
100

Sample Output

2
10

题意：

可以理解成这样：有n盏灯，一开始所有灯都是灭的，第1轮对序号是1的倍数的灯操作（原来亮的就熄灭，原来灭的就点亮）；第2轮对序号是2的倍数的灯操作、、、第i轮对序号是i的倍数的灯操作，直到第n轮过后，问剩下多少盏灯是亮的。

思路1：枚举，不解释

思路2：

这个问题有如下性质：

1、如果某盏灯被操作的次数是奇数，那它就是亮的（一开始是灭的）。

2、对于第i盏灯（i从1开始），如果i是完全平方数，那这盏灯被操作的次数就是奇数。

性质1是显然的：第0次是灭的，第1次是亮的，第2次是灭的。。。

性质2的证明：

对于序号为18这盏灯，它被操作的轮数是：第1轮，第2轮，第3轮，第6轮，第9轮，第18轮。被操作了6次，是偶数次。它被操作的轮数其实就是它的所有约数。一个大于1的非完全平方数的约数个数都是成对出现的，即都是偶数。而完全平方数，如16，其约数为1，2，4，8，16。是5个，因为4的平方是16，所以4只算一次。所以完全平方数的约数是奇数。

对于题目要求，序号为i的灯的被操作次数就是i的所有约数的个数a，如果a是奇数，那序号为i的灯最后就是亮的。归结起来就是如果i是完全平方数，那序号为i的灯最后就是亮的。所以题目最后求的就是1~n的完全平方数的个数。答案不难得出，就是将n开方向下取整（可以这样理解：x^2 <= n，解出x = 根号n向下取整，那x就是满足要求的最大值，如果k属于1~x，那k^2都是完全平方数，共有x个）。

思路1代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 550
int a[M];int main()
{//freopen("in.txt","r",stdin);int n, x, i, j, ans;scanf("%d", &n);while(n--){ans = 0;memset(a, 0, sizeof(a));scanf("%d", &x);for(i = 1; i <= x; i++){for(j = i; j <= x; j += i){if(a[j]) a[j] = 0;else a[j] = 1;}}for(i = 1; i <= x; i++)if(a[i]) ans++;printf("%d\n", ans);}return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>int main()
{//freopen("in.txt","r",stdin);int n, x;scanf("%d", &n);while(n--){scanf("%d", &x);printf("%d\n", (int)sqrt(double(x)));}return 0;
}

这篇关于开灯问题 —— POJ 1218 THE DRUNK JAILER的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！