CF1858C Yet Another Permutation Problem

Yet Another Permutation Problem - 洛谷

这题本来很简单，思路我也想到了，但是代码一直没写对，思路也一直换来换去（悲

然而发现最开始的思路是对的

题意

Alex 收到了一个名为 "GCD 排列" 的游戏作为生日礼物。这个游戏的每一轮进行如下操作：

• 首先，Alex 选择一个整数序列$a_1,a_2,…,a_n$ ，其中整数范围从 $1$ 到 $n$ 。
• 然后，对于每个 i 从 1 到 n ，计算整数 $di=gcd(ai,a(imodn)+1)$ 。
• 本轮的得分是 $d_1,d_2,…,d_n$ 中不同数字的数量。

Alex 已经玩了几轮游戏，所以他决定找一个整数序列 $a_1,a_2,…,a_n$ ，使得它的得分尽可能地大。

回顾一下，$gcd(x,y)$ 表示 $x$ 和 $y$ 的 最大公约数（GCD），而 $x\space mod\space y$ 表示将 $x$ 除以 $y$ 的余数。

长度为 $n$ 的排列是一个由 $n$ 个不同整数组成的数组，整数范围从 $1$ 到 $n$ 且顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数组中有重复的 $2$），$[1,3,4]$ 也不是排列（虽然 $n=3$，但数组中有 $4$）。

思路

可以发现，如果想让$d$里面有尽量多的不重复数字，就要让$a$中的每个数字都被利用。即，尽量使$a_i=2\times a_{i-1}$

另：不要过于参考样例，没啥用

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,cnt,f[maxn];
int run()
{
	cin>>n;
	for(int i=0;i<=n;i++) f[i]=0;
	for(int i=1;i<=n;i++)
	{
		int cnt=i;
		if(f[i]==0)
		{
			while(cnt<=n)
			{
				cout<<cnt<<" ";
				f[cnt]=1;
				cnt*=2;
			}
		}
	}
	cout<<endl;
	return 0;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		run();
	}
	return 0;
}