P11132 【MX-X5-T4】「GFOI Round 1」epitaxy

用户头像 发布于 3 天前 10 次阅读 OI

P11132 【MX-X5-T4】「GFOI Round 1」epitaxy

考虑到 nn 一定会有贡献，当把 nn 放在第 mm 个时，前 m−1m-1 个数一定没有任何贡献。
所以找到贡献最大的，作为最终的 GCD，其余从大到小放即可。

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+5;
int T,n,m;
int ans[N],tag[N];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		for(int i=1;i<=n;i++) ans[i]=tag[i]=0;
		cin>>n>>m;
		ans[m]=n,tag[n]=1;
		int mx=-1,mi;
		for(int i=n-1;i>=n-m;i--) if(__gcd(n,i)>mx) mx=__gcd(n,i),mi=i;
		int sum=mi;
		for(int i=2;i*m<=n;i++) ans[i*m]=sum,tag[sum]=1,sum-=mx;
		int idx=1;
		for(int i=n;i>=1;i--){
			if(!ans[i]){
				while(tag[idx]&&idx<n) idx++;
				ans[i]=idx,tag[idx]=1;
			}
		}
		for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
		cout<<"\n";
	}
	return 0;
}