Details of the latest application analysis of HDOJ 1443 Joseph ring

K k girls and boys stand in a line, k is in front of the boy, the k is a girl, from the first boy started to count off, check-in queues last classmate, circulation first continue to report to the team, and if a fellow student registration number is m, the students can break the ranks, and then move from 1 at the back of the classmates started to count off, now a number m, the k girls all break the ranks, and boys don't break the ranks.

Input: number of boys and girls k(equal number of boys and girls are k, output: m value
Example: input: 2, output: 7
Input: 4, output: 30

In this case, Joseph recursion formula is first introduced into the deformation of Joseph ring, and n individuals (0,... Number, n - 1), m, is the first I round out for f (I) = (f (I - 1) + m - 1) % (n - I + 1), f (0) = 0. F (I) represents the person to exit from the current subsequence (the current sequence number is 0~(n- I));
Take an example: K=4,M=30;

f(0)=0;
      f(1)=(f(0)+30-1)%8=5;  Sequence ( 0,1,2,3,4,5,6,7 ) in the 5
      f(2)=(f(1)+30-1)%7=6;  Sequence ( 0,1,2,3,4,6,7 ) in the 7
      f(3)=(f(2)+30-1)%6=5;  Sequence ( 0,1,2,3,4,6 ) in the 6
      f(4)=(f(3)+30-1)%5=4;  Sequence ( 0,1,2,3,4 ) in the 4
      ........

The first K exits must be the last K, so as long as there is one f(I) in the first K. < K then m does not answer the question.
Note:
There are several points to note in this question, otherwise it is easy to time out;
The first point, By using the formula j=(j+m-1)%(n- I), we can deduce which position the next element appears in, if j < K does not answer the question.
The second point, It is m. When only k+1 is left, the last lost number must be on the left or right side of the bad, so m%(k+1)==0 or 1
With these two conditions, you can speed up the program...
The complete implementation code is as follows:

#include "stdio.h"
#include "stdlib.h"
int x[15];

int test(int k,int m)
{
 int i,j=0,len=k*2;
 for(i=0;i<k;i++)
 {
  j=(j+m-1)%(len-i);    //Joseph ring formula
  if(j<k)
   return 0;     //If there is less than k in the previous k round, it will return 0
 }
 return 1;
}
/*
 Next up m The range of the value of k+1 The personal case, where one of the bad guys is still alive, 
 So the end position in this round must be the last bad guy, so where do we start? That's where the search comes in K+2 The end position of the individual, 
 However, K+2 The end position of the individual must be the first K+2 Personal or personal K+1 Individuals, so there are two orders: GGGG.....GGGXB  or   GGGG......GGGBX (X Said a K+2 The person that round exits) so there is K+1 There are two possible positions at the beginning of an individual's round: the last position or K+1 The position of m There are two possibilities: 
GGGG......GGGBX  if K+2 The end of the individual is in the last position ( The first K+2 a ) , m%(k+1)==0
GGGG......GGGXB  if K+2 The end of the individual is in the penultimate position ( The first K+1 a ) , m%(k+1)==1 
*/
void Joseph(void)
{
 int m,k;
 for(k=1;k<15;k++)
 {
  m=k+1;
  while(1)
  {
   if(test(k,m))     //M % (k + 1) = = 0
   {
    x[k]=m;
    break;
   }
   if(test(k,m+1))     //M % (k + 1) = = 1
   {
    x[k]=m+1;
    break;
   }
   m+=k+1;
  }
 }
}
int main(void)
{
    int k;
 Joseph();
 while(scanf("%d",&k),k)
  printf("%dn",x[k]);
 system("pause");
}