---
title: UVa 10015
toc: no
categories: 題解 UVa 數論 DP_動態規畫
...

網址
====

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