http://poj.org/problem?id=1218
数论
很有意思的题目描述，在纸上画1~10的例子，能想到一个模型：找到编号（1,2,3...n-1,n）的因子个数是奇数的囚犯，就是最后逃跑的。
容易发现：“完全平方数的因子个数为奇数”
可以直觉上"证明"一下： 完全平方数 <---> 因子个数为奇数
对于任意整数n，都可以分解为2个整数a,b的乘积，a * b == n
如果a为n的一个因子，那么 n/a 也一定为n的一个因子，可以理解为n的因子总是成对出现，所以因子总数经常是偶数，
除非存在一个因子a，使n/a==a，这样因子总数就是奇数了，显然此时n为完全平方数
整数n的因子个数：
根据算术基本定理，对n进行标准分解
n=(p1)^a1* (p2)^a2* …... * (pn)^an, 其中p1,p2,......,pn 是互不相等的质数
然后由乘法原理：n的因子个数 = (a1+1)* (a2+1)* ......* (an+1);
完全平方数的因子个数是奇数：
因为n是完全平方数，
所以a1,a2,…,an都是偶数，a1+1,a2+1,…,an+1都是奇数，
所以(a1+1)* (a2+1)*……* (an+1)是奇数。
题目就变成了求sqrt(n)的大水题。。。用库函数，二分查找，数学方法迭代，打表什么的~都可以
直接sqrt...
1 #include <stdio.h>
2 #include <math.h>
3
4 int main()
5 {
6 int t, n;
7 scanf("%d", &t);
8 while(t-- && scanf("%d", &n))
9 {
10 printf("%d\n", (int)sqrt(n));
11 }
12 return 0;
13 }
可以二分查找，理论上比直接用库函数快吧。。。
1 #include <stdio.h>
2
3 int bs(int l, int r, int x)
4 {
5 int m;
6 while(l < r)
7 {
8 m = (l + r)>>1;
9 if(m*m < x)
10 {
11 l = m + 1;
12 }
13 else
14 {
15 r = m;
16 }
17 }
18 if(l*l != x)
19 {
20 l --;
21 }
22 return l;
23 }
24
25 int main()
26 {
27 int t, n;
28 scanf("%d", &t);
29 while(t-- && scanf("%d", &n))
30 {
31 printf("%d\n", bs(1,11,n));
32 }
33 return 0;
34 }
数学方法迭代
这个方法最多只要4次就能计算出[1,100]误差<1的精确解，写的比较省略直接算4步了。。。貌似比二分还快？
1 #include <stdio.h>
2
3 int sqrt(int a)
4 {
5 double x = a/2.0;
6 int i;
7 for(i=0; i<4; i++)
8 {
9 x = (x+a/x)/2;
10 }
11 return x;
12 }
13
14 int main()
15 {
16 int t, n;
17 scanf("%d", &t);
18 while(t-- && scanf("%d", &n))
19 {
20 printf("%d\n", sqrt(n));
21 }
22 return 0;
23 }
打表。。。速度更快
1 #include <stdio.h>
2
3 int sqrt[101] = {0,1,1,1,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,10};
4
5 int main()
6 {
7 int t, n;
8 scanf("%d", &t);
9 while(t-- && scanf("%d", &n))
10 {
11 printf("%d\n", sqrt[n]);
12 }
13 return 0;
14 }
//其实这题，用简单的模拟也能AC，之所以磨叽这么多，因为想起了一些人一些事。。。
大一的时候，没几个人知道ACM，学校里也没有编程比赛，软件学院10周年院庆，办了一次C语言程序设计大赛。。。问了一下，竟然是人工判题，我和他们提建议，说了ACM模式和OJ怎么怎么好。。。当时情景历历在目，某学生会主席：“ACM是啥？你听过吗？(问旁边人)，我这大四的，都没听过”。忘了当时怎么回应的了，反正是没让着他，第一次感觉到学生会的恶心。
之后迎来了我的第一次ACM比赛——2011年ACM辽宁省赛，在大连玩得很爽，回到学校之后，这个比赛就开始了。孙宇飞+李东+我，准备一起去，比赛时候，遇到了类似本题的一道题，简单模拟，宇飞神想到有数学方法，因为其他题也做完了，想快点AK，就用数学方法做的。因为是人工判题，来了一个学长，检查代码，说这么做不行，又叫来了一个男老师，说“这是编程比赛，不是数学比赛”。。。然后我和老师吵起来了。。。宇飞学长说我“偏激”，我确实很“偏激”~可能是当时太年轻吧，比较冲动，如果换成现在的我，或许。。。可能还是得吵起来= =!只记得当时好像气得要不行了。。。这时奇迹发生了--->停电^_^，因为电脑有还原卡，原来的代码都没了，突然很爽的感觉有木有，哈哈。来电之后那老师在黑板上重新出一道题，等他写完的时候，我快敲完了，第一个完成，然后意料之中的各种挑毛病，过了半个小时才有第二个人完成，我还得了第二。。。无所谓，垃圾比赛。
弱校真的是很无奈。。。一群这样的学生和老师，如果SUTACM能把 “散落的龙珠” 召集在一起，这就是最大的意义吧。集训队也是，开发组也是，最重要的不是成绩，是人才，希望更多的牛人能加入我们。
两年之后，学校慢慢开始支持ACM，办了三届ACM校赛，有了ACM实验室。。。虽然花费了很多精力，希望一切都值得。好希望我大一时候也有这样的环境啊，
懂得珍惜