O(n)的数学解法
设对编号为0,1,...,n-1的人中第K个去掉,对于规模为n的,显然第一次去掉的是编号为K-1,这样去掉一个人后就变为规模为n-1的问题了
所以如果知道f[n-1]的结果,就能推出f[n]的结果了。观察:
f(n) f(n-1)
0 ---> n-K
1 ---> n-K+1
2 ---> n-K+2
.
.
K-2 ---> n-2
K-1 ---> n-1
K ---> 0
K+1 ---> 1
.
n-1 ---> n-K-1
可以看出,f(n) = (f(n-1)+K)%n
所以得通项公式 f(0)=0;
f(n)=(f(n-1)+K)%n
如poj 1012 2359
O(logn)的解法,具体数学的