分享到plurk 分享到twitter 分享到facebook

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