洛谷P9573 「TAOI-2」核心共振 题解

Problem

Solution

很容易发现如果 \(p\ge 2n\) 时「共振」的次数一定为 \(0\)，所以这时随便怎么输出都行。

考虑一般情况。

首先为 \(p\) 的倍数的数肯定无法与其他不是 \(p\) 的倍数的数组，所以先输出是 \(p\) 的倍数的数。

然后可以想到只需要枚举一个 \(i\) 表示余数，发现只需要枚举 \(1\) 到 \(p\div 2\) 就行（因为要两两余数配对），然后从 \(i\) 开始，每次加 \(p\) 保证余数不变，然后判断这个数有没有超 \(n\)，如果没有就输出，然后再判断与之余数相对应的数，容易想到（假设这个数为 \(j\)）对应的数即为 \(j-i+p-i\)，然后和 \(j\) 一样的判断即可。

注意如果 \(i=p-i\) 时不用考虑 \(j\) 对应的数，因为 \(j\) 对应的数的余数也是 \(i\)​。

可以证明不会有遗漏的数。

Code

#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define FOR(i,a,b) for(int i=(a);i>=(b);i--)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

int n,p;
void solve()
{
	cin>>n>>p;
	if(p>=2*n){For(i,1,n)cout<<i<<" ";cout<<"\n";return ;}
	for(int i=p;i<=n;i+=p)cout<<i<<" ";
	For(i,1,p/2)
		for(int j=i;j<=n;j+=p)
		{
			cout<<j<<" ";
			if(i!=p-i)
				if(j+p-2*i<=n)
					cout<<j-i+p-i<<" ";
		}
	cout<<"\n";
}
int main()
{
	IOS;
	int T;cin>>T;
	while(T--)solve();

	return 0;
}