传统题 100ms 256MiB

【入门】约瑟夫环

题目描述

\hspace{15pt}有 nn 个人(编号 0∼n−10\sim n-1)围成一圈,从编号为 kk 的人开始报数,报数依次为 1,2,…,m1,2,\dots,m,报到 mm 的人出队。下次从出队者的下一个人开始重新报数,循环往复,直到队伍中只剩最后一个人,该人即"大王"。

\hspace{15pt}给定三个正整数 n,k,mn,k,m,请输出最后剩下的"大王"编号。

输入格式

第一行一个正整数 TT 表述数据组数

接下来 TT 行,每行中输入三个整数 n,k,mn, k, m,用空格隔开。

输出格式

对于每组数据输出一个整数,表示最后剩下的"大王"编号。

1
5 1 2
3

数据范围与提示

【样例 1 解释】

  • 初始队列编号为 [0,1,2,3,4][0,1,2,3,4],从编号 11 开始报数:
  • 1(1),2(2)→2\hspace{8pt}1(1),2(2)\to 2 出队,剩余 [0,1,3,4][0,1,3,4];
  • 3(1),4(2)→4\hspace{8pt}3(1),4(2)\to 4 出队,剩余 [0,1,3][0,1,3];
  • 0(1),1(2)→1\hspace{8pt}0(1),1(2)\to 1 出队,剩余 [0,3][0,3];
  • 3(1),0(2)→0\hspace{8pt}3(1),0(2)\to 0 出队,剩余 [3][3],输出 33。

【数据范围】

  • 1≤T≤1001 \le T \le 100
  • 2≤n≤1002 \leq n \leq 100
  • 0≤k≤n−10 \leq k \leq n-1
  • 1≤m≤1001 \leq m \leq 100