2013
11-12

# A New Joseph Problem

Newman and Bamboo are good friends. One day, Newman taught Bamboo the famous Joseph Problem: there are N persons numbered 1 to N standing round a circle. They stand clockwise according to their numbers (namely 1, 2, 3, 4, …, N). Then, starting from 1, the killer kills every 2nd person he counts until there is only one person left whose number is J(N). We can easily infer that J(1) = 1, J(5) = 3 and J(6) = 5. Bamboo finds this problem intriguing and starts thinking. Suddenly, he finds that if he continually uses J(N) to be the term in J, he can finally get a fixed number. For example, J(2) = 1, so J(J(2)) = 1, J(J(…J(2)…)) = 1. Newman agrees with Bamboo but Bamboo is not satisfied. Furthermore, Bamboo wants to know what the fixed number will be for a specific N. Can you help us?

Only one line containing n (1 ≤ n ≤ 1010000).

Only one line containing K such that J(J(J(JJ(N)…))) = K and J(K)=K.

10

3

J(10) = 5, J(5) = 3, J(3) = 3.

//* @author
import java.io.*;
import java.util.*;
import java.math.*;
public class Main
{
public static int a[];
public static int luckpeople(int n)
{
if(n==1)
return 1;
if(n%2==1)
return luckpeople((n-1)/2)*2+1;
else
return luckpeople(n/2)*2-1;
}
public static int fun(int n)
{
int b;
while(true)
{
b=a[n];
if(b==n)
return b;
n=b;
}
}
public static void main(String[] args)
{
int i,count;
//a = new int[110];
//for(i=1;i<=100;i++)
//System.out.println(luckpeople(i));
//a[i]=luckpeople(i);
//for(i=1;i<=100;i++)
//System.out.println(fun(i));
BigInteger n,ans;
String s;
Scanner cin = new Scanner (System.in);
while(cin.hasNext())
{
n = cin.nextBigInteger();
s = n.toString(2);
count = 0;
for(i=0;i< s.length();i++)
if(s.charAt(i)=='1')
count++;
ans=BigInteger.valueOf(2);
ans = ans.pow(count);
ans = ans.subtract(BigInteger.ONE);
System.out.println(ans);
}

}

}

1. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）