 # FAKEGCD - EDITORIAL

Setter: S.Manuj Nanthan
Tester: Anshu Garg
Editorialist: Keyur Jain

Easy

# PREREQUISITES

Greatest Common Divisor

# PROBLEM

You are given an integer N. Output a permutation of values from 1 to N that satisfies the following condition:

• \gcd([1+A_1,2+A_2,3+A_3,\dots,N+A_N]) > 1

It can be proven that a solution always exists. If there are multiple permutations that can satisfy the condition, then output any one of them.

As a reminder,

• A permutation of values from 1 to N is an array containing integers from 1 to N in any order but each of them appearing exactly once.
• GCD stands for Greatest Common Divisor. The greatest common divisor of a sequence is the largest integer d such that all the numbers in sequence are divisible by d. For more information, refer to here.

# EXPLANATION

We need to ensure that \gcd([1+A_1,2+A_2,3+A_3,\dots,N+A_N]) > 1. Here are two simple ways to achieve this.

• make gcd = 2 by pairing numbers with the same parity. One such solution would be [1, 2, 3, 4 \dots, N]. This makes our resulting sequence = [1 + 1, 2 + 2, 3 + 3, \dots, N + N] which has gcd = 2

• make gcd = N + 1 by using the sequence [N, N-1, N-2 \dots, 2, 1]. This makes our resulting sequence = [1 + N, 2 + N - 1, \dots, N + 1]. This sequence has gcd = N + 1 since every element is N + 1

many more solutions are possible, but the above two are the simplest.

# TIME COMPLEXITY

The time complexity is O(N)

# SOLUTIONS

Setter's Solution
``````def inp():
return int(input())
def st():
return input().rstrip('\n')
def lis():
return list(map(int,input().split()))
def ma():
return map(int,input().split())
t=inp()
while(t):
t-=1
n=inp()
a=[i for i in range(n,0,-1)]
print(*a)
``````
Tester's Solution
``````#include<bits/stdc++.h>
using namespace std ;

#define ll              long long
#define pb              push_back
#define all(v)          v.begin(),v.end()
#define sz(a)           (ll)a.size()
#define F               first
#define S               second
#define INF             2000000000000000000
#define popcount(x)     __builtin_popcountll(x)
#define pll             pair<ll,ll>
#define pii             pair<int,int>
#define ld              long double

const int M = 1000000007;
const int MM = 998244353;

template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }

#ifdef LOCAL
#define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 2351
#endif

long long readInt(long long l,long long r,char end){
long long x = 0;
int cnt = 0;
int first =-1;
bool is_neg = false;
while(true) {
char g = getchar();
if(g == '-') {
assert(first == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if(cnt == 0) {
first = g - '0';
}
++cnt;
assert(first != 0 || cnt == 1);
assert(first != 0 || is_neg == false);

assert(!(cnt > 19 || (cnt == 19 && first > 1)));
}
else if(g == end) {
if(is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
string ret = "";
int cnt = 0;
while(true) {
char g = getchar();
assert(g != -1);
if(g == end) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

//RNG based on mersenne_twister
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int _runtimeTerror_()
{
int N;
vector<int> odd, even;
for(int i=1;i<=N;++i) {
if(i % 2 == 1) {
odd.push_back(i);
}
else {
even.push_back(i);
}
}
shuffle(all(odd),rng);
shuffle(all(even),rng);
for(int i=1;i<=N;++i) {
if(i % 2 == 1) {
cout << odd.back() << "\n";
odd.pop_back();
}
else {
cout << even.back() << "\n";
even.pop_back();
}
}
return 0;
}

int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef runSieve
sieve();
#endif
#ifdef NCR
initialize();
#endif
int TESTS = 1;
//cin >> TESTS;
while(TESTS--)
_runtimeTerror_();
assert(getchar() == -1);
return 0;
}
``````
Editorialist's Solution
``````  static class FakeGCD {
public void solve(int testNumber, InputReader in, OutputWriter out) {
Feel free to share your approach. Suggestions are welcomed as always. 