#include "svector.hpp"
unsigned find_lucky1(unsigned n, unsigned d)
{
  svector<bool> v(n);                   // n个成员，开始全部false
  for(unsigned i = 0, k = n; k > 1; --k)
  {                                     // 时间复杂度O(n*i)= O((n-1)*d*(d-1/2))
    unsigned j = 0;                     // = O(n*d*d)
    while(j < d)
    {
      if(!v[i])
        ++j;
      i = (i + 1) % n;                  // 注意循环处理下标
    }
    v[(i + n - 1) % n] = true;          // 置真表示删除
  }
  unsigned th;
  for(th = 0; th < n && v[th]; ++th);  // 为假者即最后剩余
  return ++th;                         // th为下标, 第nth + 1个
}

unsigned find_lucky2(unsigned n, unsigned d)
{
  svector<unsigned> v;
  v.reserve(n);
  for(unsigned i = 0; i < n; ++i)
    v.push_back(i);
  for(unsigned i = 0; v.size() > 1; i = (i + v.size() - 1) % v.size())
  {
    for(unsigned j = 0; j < d; ++j)
      i = (i + 1) % v.size();
    v.erase(v.begin() + i);
  }
  return v.front();
}

unsigned find_lucky(unsigned n, unsigned d)
{
	if(n < (d * d * d << 1))
	  return find_lucky1(n, d);
	else
	  return find_lucky2(n, d);
}
