UVa 10015
網址
http://uva.onlinejudge.org/external/100/10015.html
題目概述
此題為 Josephus Problem 的變形
給定一個 n 代表 n 個人,編號從 1 ~ n,從第一個人開始數,數到某個數字的人會被殺掉 ( Josephus Problem 的基本題型為固定數字 m )
此題的某個數字為質數,依序為 2, 3, 5, 7, 11 由小到大照順序,每次殺完人都要重頭開始數,
請問最後活下來的人的編號為何?
Technique details
1 <= n <= 3501
輸入格式
此題有多個測資,每個測資一行,每一行有一個數字 n
n = 0 的時候結束
輸出格式
每個測資輸出一行,輸出最後活下來的人的編號
解題思路
用 Josephus Problem 的 DP 式
for (int i=1; i<=n; ++i)
ans = (ans + m) % i;
要把 m 改成質數,從大質數開始加
m -> p[n-i] //p為質數表的list