首页 > 专题系列 > Java解POJ > POJ 2800 Joseph’s Problem [解题报告] Java
2013
11-12

POJ 2800 Joseph’s Problem [解题报告] Java

Joseph’s Problem

问题描述 :

Joseph likes taking part in programming contests. His favorite problem is, of course, Joseph’s problem.

It is stated as follows.

    There are n persons numbered from 0 to n – 1 standing in a circle. The person numberk, counting from the person number 0, is executed. After that the person number k of the remaining persons is executed, counting from the person after the last executed one. The process continues until only one person is left. This person is a survivor. The problem is, given n and k detect the survivor’s number in the original circle.

Of course, all of you know the way to solve this problem. The solution is very short, all you need is one cycle:

	r := 0;

for i from 1 to n do
r := (r + k) mod i;
return r;

Here “x mod y” is the remainder of the division of x by y, But Joseph is not very smart. He learned the algorithm, but did not learn the reasoning behind it. Thus he has forgotten the details of the algorithm and remembers the solution just approximately.

He told his friend Andrew about the problem, but claimed that the solution can be found using the following algorithm:

	r := 0;

for i from 1 to n do
r := r + (k mod i);
return r;

Of course, Andrew pointed out that Joseph was wrong. But calculating the function Joseph described is also very interesting.

Given n and k, find 1<=i<=n(k mod i).

输入:

The input file contains n and k (1<= n, k <= 109).

输出:

Output the sum requested.

样例输入:

5 3

样例输出:

7

解题代码:

//* @author: Yeming Hu"[email protected]"
import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
	long n,k;
	while(sc.hasNext())
	{
	    n = sc.nextLong();
	    k = sc.nextLong();
	    long sum;
	    if(n<=k)
	    {
	        sum = sumMod(k,n);
	    }else
	    {
	        sum = sumMod(k,k);
		sum += (n-k)*k;
	    }

	    System.out.println(sum);
	}
    }

    static long sumMod(long k, long n)
    {
        long sum = 0;
	long d = k/n;
	long t1 = n;
	long t2 = k/(d+1);
	while(k/d - t2 > 10)
	{
	    long s = k%t1;
	    long e = k%(t2+1);
	    sum += (s+e)*(t1-t2)/2;
	    d++;
	    t1 = t2;
	    t2 = k/(d+1);
	}

	for(long i=2;i<=t1;i++)
	{
	    sum += k%i;
	}

	return sum;
    }
}

  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 问题3中,GetRightPosition()和GetLeftPosition()与STL中的upper_bound()和lower_boune()的代码实现一样吗?