今天参加了一个IT公司的面试 有两道开放性试题没答上来 谁能帮帮忙 讲一下答案和道理

Question

在一条长长的走廊上依次排列着100把锁着的锁头，你从把这100把锁全部打开开始（第一遍）。然后，你把所有序号是2的倍数的锁头再锁上（第2遍）。接下来，你依次走到所有序号是3的倍数的锁头前，如果它是打开的，就把它锁上，如果他是锁上的，就把它打开------我们把这称为“切换锁头的状态”（第三遍）。你继续像这样在第N遍去切换所有序号是N的倍数的锁头的状态。当进行到第100遍时，你将只切换第100把锁头的状态。

请问：在如此这般地进行了100遍切换之后，有多少锁头是打开的？

Answer 1

　　答案: 进行100遍切换之后,有锁1,4,9,16.....100,共10把锁头是打开的;
　　如果走廊里依次排列着K把锁头，那么在第K遍后,有锁1,4,9,16.....,|sqrt(k)|锁头是打开的.

　　证明: 100把锁头分别标记为s1,s2,s3,..,si,..,s100
　　s1只在第1遍被切换状态;
　　如果i是素数,si只是在第1遍和第i遍被切换状态,切换次数为偶数个;
　　如果i是非平方数的合数,则总可以分解为i=m*n=q*p=....=r*u(m!=n,q!=p,....,r!=u),si只是在第1遍,第i遍,第m,n,q,p,...,r,u遍被切换状态,切换次数为偶数个;
　　如果i是平方数时,i=m*n=q*p=....=r*u=x*x(m!=n,q!=p,....,r!=u),si只是在第1遍,第i遍,第m,n,q,p,...,r,u遍,第x遍被切换状态,切换次数为奇数个;
　　切换之前,锁头是锁着的状态,经过偶数次切换后,锁头还是锁着的状态;
　　切换之前,锁头是锁着的状态,经过奇数次切换后,锁头变为打开着的状态.
　　因此,只有当i是平方数的锁头被打开.
　　算法: 由开锁智力题的操作步骤,我们可以获得启发,按照这种方法获取平方数.
　　step1:将数的状态值都设定为-1;
　　step2:将所有数依此模1,2,3,....,100,如果结果为0,就改变状态;
　　step3:打印出状态值为1的数.
　　程序: 下面是利用这一方法获取[1,100]区间上平方数的程序,代码在vc++6.0平台运行成功.
　　/**author:mapping
　　date:2007.2.15
　　FindSquareNumber .cpp**/
　　#include <iostream>
　　#include <process.h>
　　using namespace std;
　　void main()
　　{
　　int a;
　　int i;
　　for(i=1; i<= 100; i++)
　　{
　　a=-1;
　　for(int j=1;j<=i;j++)
　　{
　　if(i%j==0)
　　a=(-1)*a;
　　}
　　if(a==1)
　　cout<<"square number :"<<i<<endl;
　　}
　　system("pause");
　　}