ACM：数论专题(3)——约瑟夫问题
2016-04-21 09:25:30         来源：octopusflying的专栏

(p.s: 以前做约瑟夫问题都是用链表模拟，今天发现了一个效率更高的方法，受教了。。。)

1: 0 1 - 3 4 // 0 1 2, 2号候选人淘汰

2: - 1 3 4 // 3 4 0,0号候选人淘汰

3: 1 3 - // 1 3 4, 4号候选人淘汰

4: - 3 // 1 3 1, 1号候选人淘汰

·递推方法(1)：

f(1) = 0 (只有1个人候选人时，他就是最后的获选者).

f(x) = (k + f(x - 1)) % n.

（new + k) % n = old.

f(n) = (f(n-1) + k)%n

·递推方法(2):

old = new + n - n%k

old = (new + n - n%k) % n+ (new - n % k) / (k - 1)
= new - n%k + (new - n%k) / (k-1)

1≤t≤100
2≤n≤1,000,000,000
2≤k≤1,000

```/****************************************************/
/* File        : Hiho_Week_94.cpp                   */
/* Author      : Zhang Yufei                        */
/* Date        : 2016-04-19                         */
/* Description : HihoCoder ACM program. (submit:g++)*/
/****************************************************/

#include

/*
* This function deals with one test case.
* Parameters:
*		None.
* Returns:
*		None.
*/
void function (void);

/*
* This function get the result of the given n and k.
* Parameters:
*		@n: The number of candidate.
*		@k: The 'k' parameter in this question.
* Returns:
*		The result for the given n and k.
*/
int compute(int n, int k);

/*
* The main program.
*/
int main (void) {
int t;
scanf("%d", &t);

for(int i = 0; i < t; i++) {
function();
}

return 0;
}

/*
* This function deals with one test case.
* Parameters:
*		None.
* Returns:
*		None.
*/
void function (void) {
int n, k;
scanf("%d %d", &n, &k);

printf("%d\n", compute(n, k));
}

/*
* This function get the result of the given n and k.
* Parameters:
*		@n: The number of candidate.
*		@k: The 'k' parameter in this question.
* Returns:
*		The result for the given n and k.
*/
int compute(int n, int k) {
if(n == 1) {
return 0;
}

if(n < k) {
return (k + compute(n - 1, k)) % n;
} else {
int r = compute(n - n / k, k);
if(r < n % k) {
return r - n % k + n;
} else {
return r - n % k + (r - n % k) / (k - 1);
}
}
} ```