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;
}

* The material and content uploaded on this website are for general information and reference purposes only. Please do it by your own first. COPYING MATERIALS IS STRICTLY PROHIBITED.


More from PROGIEZ