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)的解法,具體數學的