Fake GCD: FAKEGCD

link: https://www.codechef.com/CU1PP0009/problems/FAKEGCD

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

• gcd([1+A1,2+A2,3+A3,…,N+AN])>1gcd([1+A1,2+A2,3+A3,…,N+AN])>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 11 to NN is an array containing integers from 11 to NN 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 dd such that all the numbers in sequence are divisible by dd. For more information, refer to here.

Input Format

• The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
• The first line of each test case contains an integer NN.

Output Format

For each test case, output on one line a permutation of values from 11 to NN which satisfies the above condition.

Constraints

• 1≤T≤5001≤T≤500
• 2≤N≤5002≤N≤500

Sample Input 1 

1
4

Sample Output 1 

3 4 1 2

Explanation

• For the first test case, gcd([1+3,2+4,3+1,4+2])=gcd([4,6,4,6])=2gcd([1+3,2+4,3+1,4+2])=gcd([4,6,4,6])=2 which is greater than 11, so the given permutation satisfies the condition.

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 readString(int l,int r,char end){
    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){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}

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

int _runtimeTerror_()
{
    int N;
    N = readIntLn(2,500);
    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;
    TESTS = readIntLn(1,500);
    while(TESTS--)
        _runtimeTerror_();
    assert(getchar() == -1);
    return 0;
}

---

---

More from PROGIEZ