AOJ1275:And Then There Was One
解き方
継子立てのバリエーション。(ヨセフスの問題とも言うらしい)
http://ja.wikipedia.org/wiki/%E3%81%BE%E3%81%BE%E3%81%93%E7%AB%8B%E3%81%A6
1,2,...,nのn人を円形にclockwiseに並べ、1からclockwiseに数えてk人目を抜くという操作を繰り返す。
n人からk番目ごとに抜き出していった時に、1人目から数えてf(n)番目の人が残るとする。
ここでf(n)=(m-1+f(n-1)) mod n + 1が成り立つ。(f(1)=1)
(ここが若干解りにくい。k個置きに抜く、0-indexedで計算するとf(n) = (k+f(n-1) mod n)になる)
これで誰が残るかは解るものの、この問題では始めの番号が指定されているので、
どこを1とすると1からk人ごとに抜いていったときに始めにkが抜かれるかを計算し、それをbiasとして
とっておく。
最終的に出てきた答えにbiasをかけてやればok。
