今年的刘谦给全国观众带来了俩魔术，一个是洗牌一个是撕牌，前面第一个魔术看不出来太神奇了，但是第二魔术感觉挺有趣的我可以简单分析分析。

然后我们列出这个魔术的关键步骤：

1. 打乱四张牌
   1 2 3 4

2. 对折、撕开、面向同一个方向重叠
   1 2 3 4 1 2 3 4

3. 名字几个字久循环放几张
   4 1 2 3 4 1 2 3

4. 拿三张牌插中间
   3 4 4 1 2 1 2 3

5. 第一张牌藏起来
   4 4 1 2 1 2 3

6. 南方人移动一张牌至中间；北方人移动一张牌至中间；不南不北移动三张至中间
   4 1 2 4 1 2 3

7. 分类讨论

8. 男生（以男生为例子，女生一样的）

   1. 扔一张
      1 2 4 1 2 3

   2. 念"见证奇迹的时刻"
      2 4 1 2 3 1

   3. “好运留下来”，每次移动一张牌至底部，然后丢掉一张牌，反复直到剩下一张牌
      2 1 2 3 1
      2 1 3 1
      2 1 3
      2 3
      3

9. 女生

   1. 扔两张
      2 4 1 2 3

   2. 念"见证奇迹的时刻"
      1 2 3 2 4

   3. “好运留下来”，每次移动一张牌至底部，然后丢掉一张牌，反复直到剩下一张牌、
      1 2 3 2 4
      1 3 2 4
      1 3 4
      3 4
      3

以上就是全部的过程，我们可以发现魔术中虽然又名字或者是南北方或者是性别的区分，但是基本上到第四步都是一样的，在第四步的时候一定会有两张一样的牌分别在一开始还有最后，这个是因为前面无论你循环移动多少多少张牌都是按照12341234循环，然后再拿掉三张牌放中间必然前面后面是一样的牌。
把第一张牌藏起来之后，选择任意数量牌插入中间这个也不影响了，因为我们此时的目标牌是最后一张，只要数量不要太大不影响。
最后就是男生和女生的分类进行扔牌操作，其实就是一个约瑟夫环问题，把一张牌放到底部然后扔掉一张牌，那不就是约瑟夫环中的每隔一个数去掉一个数嘛，最终问题化简为找最后剩下那一张牌的位置。
男生是剩下七张牌，所以我们需要找到的位置是倒数第二个，女生剩下的牌数是六张牌，所以我们需要找到的位置是第三个。也就是说在"好运留下来"环节之前我们需要把原本的最后一张牌的位置调整到对应的位置。这里涉及到同余思想，男生需要移动到这个位置需要的次数除以6余1，女生需要移动到这个位置需要的次数除以5余2，所以最小的移动次数就是7，正好对应"见证奇迹的时刻"七个字。
那至于约瑟夫环问题如何快速知道最后那个位置在哪里呢？

问题描述：有n个人（编号从1到n）站成一个圆圈。从编号为1的人开始报数，数到m的那个人出列，然后从出列的下一个人开始重新报数，循环执行，直到所有人都出列。问题的目标是确定第i个淘汰的人编号。
思路：
1、当i较小时：ysf(int n,int m,int i)：这个递归函数代表的意思为：有n个人，报到数字m时出局，求第i个人出局的编号。

$ysf(n,m,i)=\{\begin{array}{ll}(ysf(n-1,m,i-1)+m)\%n& \text{i>1}\\ (M-1+N)\%N& \text{i=1}\end{array}$

2、当m较小时：每一次都是加k的操作，因此有很多时候这个%n很多时候都是没有用的，因此我们可以一次就将这些k都加上，以此来降低复杂度。
直接使用：

ll ysf(ll n, ll m, ll i)          //按顺序递归枚举 n表示当前剩余数量 m表示淘汰数量 k表示间隔人数
{
    if (i == 1) return (m - 1 + n) % n;   //只有一个的时候可以直接输出答案
    return (ysf(n - 1, m, i - 1) + m) % n;
}

ll ysf2(ll n, ll m, ll i)
{
    ll ct= n - i + 1;                    //表示当前剩余个数，从小往大枚举
    ll val= (m - 1) % ct;                //当前淘汰位置
    ll dang_qian=1;                 	//已经淘汰的个数
    while(dang_qian < i)
    {
        if(val + m >= ct + 1)             //下一个淘汰的位置已经超过本圈人数
        {
            ct++;                   //当前的总人数加一
            val= (val + m) % ct;         //计算新的一圈起点
            dang_qian++;            //计算当前淘汰的人数
            continue;
        }
        ll x=(ct-val-1)/(m - 1);      //计算本圈可以淘汰多少人
        x=min(x, i - dang_qian);      //如果本圈淘汰的人已经足够了取m-dang_qian
        dang_qian+=x;               //计算当前已经淘汰的人数
        val= val + m * x;                //计算当前淘汰的位置
        ct+=x;                      //计算当前剩余的人数
    }
    return val;
}

void solve()
{
    ll n,m,k;
    read(n);				//输入
    read(m);
    read(k);
    if(k==1)
    {
        printf("%lld\n",m);
        return ;
    }
    if(m<=(ll)1e6)printf("%lld\n",ysfdg(n,k,m)+1);     //直接按顺序枚举
    else    printf("%lld\n",ysf2(n,k,m)+1);
}