题目：

Description

定义a[l,r] = { a[l] , a[l+1] , a[l+2], … a[r-1] , a[r] }

定义mex函数：mex(l,r) = 不存在于a[l,r]内的最小非负整数

定义k阶Mex数列：Mex(n)=

n (n<k)

mex(n-k,n-1) (n>=k)

a[i]=Mex(i)

Input

第一行输入一个整数T，表示有T组数据。(1<=T<=100000)

每组数据输入两个整数n,k(0<=n<=1000000000,1<=k<=1000000000)

Output

输出k阶Mex(n)的结果

Sample Input

2

1 1

3 5

Sample Output

1

3

---

问题分析：

第一次看到这道题时，感觉逻辑很绕，像是闭环套娃一样，图解如下：

第一想到的是用递归去解这道题，然后尝试写了几段代码，如下：

#include <stdio.h> int a[1000000000]; void quicksort ( int left, int right ); long long int Mex(long long int n, long long int k ); long long int mex( long long int l, long long int r, long long int k ); int main() { long long int t,n,k,i; scanf ( "%lld", &t ); while ( t-- ) { scanf ( "%lld %lld", &n, &k ); printf ( "%lld", Mex(n,k) ); } return 0; } //快速排序算法本体 void quicksort ( int left, int right ) { int i, j, t, temp; if ( left>right ) return; i = left; j = right; temp = a[left]; while ( i!=j ) { while ( a[j]>=temp && i<j ) j--; while ( a[i]<=temp && i<j ) i++; if ( i<j ) { t = a[i]; a[i] = a[j]; a[j] = t; } } a[left] = a[i]; a[i] = temp; quicksort ( left, i-1 ); quicksort ( i+1, right ); } long long int Mex(long long int n, long long int k ) { //最简单的情况 if ( n<k ) { return n; } else { return mex( n-k, n-1, k); } } long long int mex( long long int l, long long int r, long long int k ) { long long int temp; int i; //创建数组 for ( i=l; i<=r; i++ ) { a[i] = Mex(i, k); } //排序数组 quicksort( l, r ); //想先用快排排序a数组 //因为数组内的值一定大于等于0 //故排序后最小的值就是a[0] //现在看这里求最小非负整好像有点小问题 temp = a[0]; while ( temp>0 ) { temp--; } return temp; }

然后就出现了令人崩溃的报错，第一次见，也毫无头绪，在网上冲浪搜索了一圈后发现果然国内的资源还是太少（主要是出现这种错误的人也少hhh），只有零零散散几个类似报错的技术博客，博主也只提出了“可能”是连接器的错误。

连接器？？？在求助师兄后，建议我换个编译器，但结果还是无济于事，另一位师兄提醒我其实这一题可以用列举法的。

一开始我还很不情愿，感觉我的算法没问题，最主要的是不知道错在哪里了！如果有知道的小伙伴请一定要留言告知 十分感谢！

在折腾了两天后，还是放弃了，走另一条路：列举 通过上图简单的证明可知数组a是0~k以k+1为周期的数组 然后再列几种情况 就很容易发现是n%（k+1）了

---

AC代码：

#include <stdio.h> int main() { int T; scanf ( "%d", &T ); while ( T-- ) { int n, k; scanf ( "%d %d", &n, &k ); printf( "%d\n", n % (k + 1) ); } return 0; }