O(n)的數(shù)學(xué)解法
設(shè)對編號為0,1,...,n-1的人中第K個去掉,對于規(guī)模為n的,顯然第一次去掉的是編號為K-1,這樣去掉一個人后就變?yōu)橐?guī)模為n-1的問題了
所以如果知道f[n-1]的結(jié)果,就能推出f[n]的結(jié)果了。觀察:
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)的解法,具體數(shù)學(xué)的