我认为本题难点不在gcd上面，而是如何放置青蛙。下面我把可以冰冻其他青蛙的称作冰冻青蛙，其他的称为普通青蛙。我发现用双端队列deque实现起来比较方便。

大致思路

  • 规划在序列中用尽量少的冰冻青蛙让所有青蛙被冰冻，下面我们用1和0表示冰冻青蛙和普通青蛙
  • 010010010···很明显这样是用最少的1使得所有青蛙都被冰冻
    • 当是类似于0100100的时候，也就是(n-1)%3==0最后一个也需要是冰冻青蛙，变成0100101
  • 用sum表示最少所需的冰冻青蛙，num变量表示实际有多少个冰冻青蛙
  • sum变量参照上面的规律可以得到，num直接遍历1~n看是不是999999999的因数就行
    • 是冰冻青蛙的放到deque的前面，不是的放到后面，达到11111000····的效果
    • 所有必须是冰冻青蛙的位置用map标记，方便之后放进去
  • 先判断一下是否可以冰冻所有青蛙，如果不行就输出Baka!
  • 再开一个ans数组表示最终的放置状态，从前往后遍历，如果这个地方必须是冰冻青蛙，即mp[i]!=0就把deque的front放进去，否则把deque的back放进去。最后直接输出即可

核心代码

void solve()
{
	cin >> n;
	vector<int> a(n+1); 
	int inf=999999999;
	unordered_map<int,int> mp;//标记哪里必须是冰冻青蛙
	int sum=0;//最少需要这么多个
	for(int i=2; i<=n; i+=3) sum++,mp[i]=1;
	if((n-1)%3==0) sum++,mp[n]=1;;
	int num=0;//实际有这么多个
	deque<int> dq;
	for(int i=1; i<=n; i++)
	{
		if(__gcd(i,inf)!=1)
		{
			num++;
			dq.push_front(i);
		}
		else dq.push_back(i);
	}
	if(num<sum)
	{
		cout << "Baka!";
		return ;
	} 
	vector<int> ans(n+1);
	for(int i=1; i<=n; i++)
	{
		if(mp[i])
		{
			ans[i]=dq.front();
			dq.pop_front();
		}
		else
		{
			ans[i]=dq.back();
			dq.pop_back();
		}
	}
	for(int i=1; i<=n; i++) cout << ans[i] << ' '; 
}