【比赛回顾】广工大2020级年ACM第一次月赛——K阶Mex数列（刷题生涯最坎坷的一道题）

题目：

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;
}