版本 44b85f580aa65b87e7803a44dcf814249cb1e378
Changes from 44b85f580aa65b87e7803a44dcf814249cb1e378 to current
---
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
