数论
很有意思的题目描述，在纸上画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 #include2 #include 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 #include2 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 else14 {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 #include2 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 #include2 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实验室。。。虽然花费了很多精力，希望一切都值得。好希望我大一时候也有这样的环境啊，
懂得珍惜