题解

思路

考虑直接构造。

解题方法

容易发现 $n$ 一定是某一段的最大值，故答案一定是 $n$ 的因数。

如果 $2m>n$，则构造 $\dfrac{n+1}{2}$ 位置是 $n$，其他位置乱填，此时任意一个区间必然包含 $n$，答案为 $n$

其余情况至少有两个最大值不同的段，考虑现在 $x$ 的倍数只有 $\dfrac{n}{x}$ 个，其中 $x$ 是答案。

若 $x>m$，则必有一段长为 $m$ 的段没有 $x$ 的倍数，故 $x\leq m$。

所以猜想此时答案是 $m$ 以下最大的 $n$ 的因数。

考虑构造：$x,1,...,x-1,2x,x+1,...,2x-1,3x,...$

然后就做完了。

复杂度

时间复杂度: $O(Tn)$

空间复杂度: $O(1)$

Code

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T;cin>>T;
	while(T--){
		int n,m;cin>>n>>m;
		if(m*2>n){
			int cnt=0;
			for(int i=1;i<=n;++i)if(i==(n+1)/2)cout<<n<<" ";else cout<<(++cnt)<<" ";
			cout<<'\n';
			continue;
		}
		int T=1;
		for(int i=m;i>=1;--i)if(n%i==0){T=i;break;}
		int cnt=0;
		for(int i=1;i<=n/T;++i){
			cout<<T*i<<" ";++cnt;
			for(int j=1;j<T&&cnt<n;++j)cout<<(i-1)*T+j<<" ",++cnt;
		}
		cout<<'\n';
	}
	return 0;
}