出處 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4140
解題策略:
(1)ans[n]為編號0到n-1的解,為剩下最後一個的編號。
假設0到n-1砍去第k個(編號k-1),剩下編號 k 、k+1 、k+2、...、n-1、0、 1 、2 、... 、k-2
重新編號為 0 、 1 、 2、...、 n-k-1、n-k、n-k+1、n-k+2、...、n-2
相當求n-1個的最後一個編號即ans[n-1],但ans[n-1]需要位移k個才會是ans[n],所以可以獲得ans[n]=(ans[n-1]+k)%n,ans[1]=0
(2)第一個砍的編號從m開始(不是k),所以ans[n]=(ans[n-1]+m)%n,第二個以後間隔k個,當i>1且i<n時,ans[i]=(ans[i-1]+k)%i。
(3)第一個真正編號為1不是0,所以需要加1,才是答案。