本文共 3575 字，大约阅读时间需要 11 分钟。

题目

Problem Description 不知道你是否玩过杀人游戏，这里的杀人游戏可没有法官，警察之类的人，只有土匪，现在已知有N个土匪站在一排，每个土匪都有一个编号，从1到N，每次杀人时给定一个K值，从还活着的土匪中，编号从小到大的找到K个人，然后杀掉，继续往下，直到找遍，然后继续从剩下的土匪中，编号从小到大找到第K个活着的土匪，然后杀掉。比如，现在有10个土匪，K为3，第一次杀掉3，6，9号的土匪，第二次杀掉4，8号土匪，第三次杀掉5号土匪，第四次杀掉7号土匪，第五次杀掉10号土匪，我们看到10号土匪是最后一个被杀掉的（从1到K-1的土匪运气好，不会被杀！）。现在给定你一个N和一个K，问你最后一个被杀掉的土匪的编号是多少。

Input

第一行有一个T（T<=10000），接下来有T组数据，每组中包含一个N（N<2^31）和一个K（3<=K<=100&&K<N）。

Output

对于每组数据，输出最后被杀的土匪的编号。

Sample Input

1 10 3

Sample Output

10

---

吐槽与碎碎念

初看这道题，脑海中立马浮现出来：“这不是XX约瑟夫环吗？看我五分钟给他敲出来！”

敲着敲着，我发现了它似乎没有表面上那么简单，而题目中2³¹的数据量，也在提醒着我，没办法直接暴力模拟QAQ

思路

不过，这看起来是和·约·瑟·夫·环·类·似·的·找·规·律·题（我flag就先立在这），对于找规律题，先打个表找找规律再说！

#include 
   
    #include 
    
     #include 
     
      using namespace std;typedef long long ll;void rua(int n, int k) {       vector
      
        v;    for (int i = 1; i <= n; ++i) {           v.push_back(i);    }    while (v.size() >= k) {           for (int i = k - 1; i < v.size(); i += k) {               v.erase(v.begin() + i);            i--;        }    }    cout << v[k - 1] << '\n';}int main() {       std::ios::sync_with_stdio(false), cin.tie(nullptr);    for (int i = 4; i <= 100; i++) {           cout << i << ":  ";        rua(i, 3);    }    return 0;}
      
     
    
   

在生成了n为4到100，k为3的结果后，我陷入了社会与人生的大思考……

4: 4

5: 5

6: 5

7: 7

8: 7

9: 7

10: 10

11: 10

12: 10

13: 10

14: 14

15: 14

16: 14

17: 14

18: 14

19: 14

20: 20

21: 20

22: 20

23: 20

24: 20

25: 20

26: 20

27: 20

28: 20

29: 29

30: 29

31: 29

32: 29

33: 29

34: 29

35: 29

36: 29

37: 29

38: 29

39: 29

40: 29

41: 29

42: 29

43: 43

44: 43

45: 43

46: 43

47: 43

48: 43

49: 43

50: 43

51: 43

52: 43

53: 43

54: 43

55: 43

56: 43

57: 43

58: 43

59: 43

60: 43

61: 43

62: 43

63: 43

64: 64

65: 64

66: 64

67: 64

68: 64

69: 64

70: 64

71: 64

72: 64

73: 64

74: 64

75: 64

76: 64

77: 64

78: 64

79: 64

80: 64

81: 64

82: 64

83: 64

84: 64

85: 64

86: 64

87: 64

88: 64

89: 64

90: 64

91: 64

92: 64

93: 64

94: 64

95: 95

96: 95

97: 95

98: 95

99: 95

100: 95

似乎，在某些范围内，结果是固定的

以及，在小于K的时候，结果为最后一个数

不过，我认认真真看了很久，并没有找到结果与n的值有什么对应的关系

那么，单纯的找通项公式什么的应该就不现实了。

不过，我还不想放弃找规律这条路 既然没法直接找到通项公式，我们还有一类规律可以试着找一下 那就是——递推关系！

先把前几项单独提出来看看：

对于k=3的情况

n	结果
4	4
5	5
6	5
7	7
8	7
9	7
10	10
11	10
12	10
13	10
14	14
15	14

对于n=4和n=5的情况，结果都为最后一项，而n=6的时候，结果却为5，而n=7时，结果为7了

这是什么情况？ 原来第一次杀人的时候，对于 1 2 3 4 5 6 7 首先3和6被干掉了 剩下了 1 2 4 5 7 之后4和5相继被干掉，最后一个被干掉的是7

所以最开始：

1 2 3 4 5 6 7 第一轮后： 1 2 4 5 7 第二轮后：1 2 5 7 第三轮后：1 2 7 第四轮，7被杀死

对于n=6时也一样，6在第一轮就被干掉了，最后被干掉的也是7

我们要找出递推关系上的规律，就要找到前后两种状态之间的关系

不管n等于几，它最后都站在了第三个位置上，而小于3的人不会被杀 所以，我们可以把第四轮作为第一种状态，也就是第三轮后 第二轮，7站在了第四个位置上，它的前面多出来了1个人 第一轮，7站在了第五个位置上，它的前面多出来了1个人 第一轮之前，7站在第七个位置上，它前面多出来了2个人

咦，这个它前面多出来的人，似乎有某种规律

我们每轮杀人，都是要杀站在3的倍数位置上的人 那我们完全可以反过来，知道我们每轮要复活的人，插在哪个位置上 死者苏生 杀站在3的倍数位置上的人，换句话说，就是每隔两个人，杀掉一个人 那我们进行复活后，也是每隔两个人，插一个人。

再来看看题目，我们每一轮都会杀掉站在3的倍数位置上的人

也就是说，每次我们杀掉的人数，是n/k向下取整 那么，我们可以用一个式子来表示，一轮前后的人数关系

前一轮的人数为n，那么后一轮就为n-n/k

不过，这与我们想知道的“最后被杀掉的人的编号”有什么关系呢？

看看我们六行前推出的结论

我们可以从第三轮后开始，在7前面，每隔两个人复活一个人，复活的人数，加上7前面的人数，就是第二轮后，7的位置 以此类推，我们就能得出在第一轮杀人之前，7所在的位置。

由此，递推的规律便找到了w

---

结论

我们设一个函数f(n,k)

用来表示最后被杀的人的编号，我们设为p 那么，它在下一轮的位置，就是f(n-n/k,k) 那么，他当前的位置f(n,k)就是f(n-n/k,k)加上他前面要复活的人数， 我们设他在下一轮的位置f(n-n/k,k)为x 那么，他前面要复活的人的数量就是(x-1)/(k-1) 复活的数量加上他下一轮的位置，就是他当前的位置 由此得出递推公式

x = f(n - n / k, k);f(n, k) = x + (x - 1) / (k - 1);

我们只要写一个递归，就能求出来啦www

#include 
   
    #include 
    
     using namespace std;typedef long long ll;ll rua(ll n, ll k) {       if (n == k)return k;    ll x = rua(n - n / k, k);    return x + (x - 1) / (k - 1);}int main() {       ios::sync_with_stdio(0), cin.tie(0);    int t;    cin >> t;    ll n, k;    while (t--) {           cin >> n >> k;        cout << rua(n, k) << '\n';    }    return 0;}
    
   

over~