专栏文章

题解：CF2137B Fun Permutation

NNottingham_Forest
CF2137B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minyn0lh
此快照首次捕获于
2025/12/02 10:29
3 个月前
此快照最后确认于
2025/12/02 10:29
3 个月前
查看原文

题目大意

给一个长度为 nn 的排列 pp，请找出另一个长度为 nn 的排列 qq，使得每一个 1≤i<n1 \le i < n，都有 gcd⁡(pi+qi,pi+1+qi+1)≥3\gcd(p_i+q_i,p_{i+1}+q_{i+1}) \geq 3。

思路

思维题。
如果我们让 qi=n−pi+1q_i=n-p_i+1，那么 qq 很明显也是一个排列，这时我们把式子化简一下可得 gcd⁡(pi+qi,pi+1+qi+1)=n+1\gcd(p_i+q_i,p_{i+1}+q_{i+1}) = n+1，因为 n≥2n \geq 2，所以 n+1≥3n+1 \geq 3，所以 gcd⁡(pi+qi,pi+1+qi+1)≥3\gcd(p_i+q_i,p_{i+1}+q_{i+1}) \geq 3。
所以这种构造是满足条件的，直接输出即可。

代码

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,p[200005];//定义
signed main()
{
	cin>>t;
	while(t--)//多测
	{
		scanf("%lld",&n);
		for(int i=1;i<=n;i++)  scanf("%lld",&p[i]);//输入
		for(int i=1;i<=n;i++)
		{
			printf("%lld ",n-p[i]+1);//输出
		}
		printf("\n");//记得换行
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...