// 无头结点的双向循环链表, 用于解决约索夫环问题
// dllist.hpp

template <typename T>

struct dlnode               // 双向循环链表的节点
{
	dlnode* prev, * next;
	T data;
	dlnode(const T& t = T()) : data(t) {}
};  // dlnode

template <typename T>
class dllist
{
private:
	dlnode<T>* head;
public:
  dllist() : head(0) {}
  ~dllist()
  {
  	if(0 == head)
  	  return;
  	dlnode<T>* p = head;
  	while(p->next != head)
  	{
  		dlnode<T>* tmp = p;
  		p = p->next;
  		delete tmp;
  	}
  	delete head;
  }

  void push_back(const T& x)
  {
  	dlnode<T>* p = new dlnode<T>(x);
  	if(0 == head)
  	{
  	  head = p;
  	  head->prev = head->next = p;
  	}
  	else
  	{
  	  head->prev->next = p;
  	  p->prev = head->prev;
  	  p->next = head;
  	  head->prev = p;
  	}
  }

  dlnode<T>* erase(dlnode<T>* p)
  {
  	dlnode<T>* next_node = p->next;
  	if(p == head)
  	  head = next_node;
  	p->prev->next = next_node;
  	next_node->prev = p->prev;
  	delete p;
  	return next_node;
  }

  dlnode<T>* header() const { return head; }
};

unsigned find_lucky(unsigned n, unsigned d)   // 失败返回-1, 成功返回序号
{
  if(10000000 < n || 1000000000 < n * d)      // 数据量过大按失败处理
	return -1;
  dllist<unsigned> dl;
  for(unsigned i = 0; i < n; ++i)
	dl.push_back(i);
  dlnode<unsigned>* start = dl.header();
  for(unsigned i = 1; i < n; ++i)             // 时间复杂度O(n*d)
  {
	  for(unsigned j = 1; j < d; ++j)
	    start = start->next;
	  start = dl.erase(start);
  }
  return start->data + 1;
}

