#include  <iostream>
using namespace std ;

int   main ()
{   int n , m , k , i ;
    
    while (scanf ("%d" , &n) != EOF && n)
    { for (m=1 ; ; ++m)
      { k = 0 ;
        for (i=2 ; i<=n-1 ; ++i)
          k = (k + m) % i ;
        if (! k)
        { printf ("%d\n" , m) ;
          break ;
        }
      }
    }
    
    return 0 ;
} 

我来简单地讲一下这道题目。
了解约瑟夫问题的人一定知道，知道了有 n 个人（0,1,...(n-1))，数的数字为 m （从0开始数，数到 (m-1) 者杀死，下一个人再从 0 开始数）我们可以用一个 O(N) 的递推算法计算出如果有 n 个人的话，最后一个死的人是谁 ：
F[1] = 0
F[i] = (F[i-1] + m) % i (i > 1)
这题我们可以通过从小到大枚举 m , 来求得解。
有一个小 Trick ：刚开始的时候 1 号城 cut 了，这实际上就是表示从 2 号城开始计数。所以这里的 2 号城就是经典问题里面的 0 号城。因此，我的程序最后只需要判断 k 是否为 0 即可。
程序跑了 16 ms ……
不过当 n = 6000 ，程序就要用 1s 多的时间了。

• 赤裸裸的枚举就是啦。 (0) 10070709 2009-12-27 15:29:01