Yet Another Permutation Problem

题意

输入一个n，求1到n的全排列中gcd[ai,a((i %n)+1)]中的不同数的数量的最大值

分析

对于如何一个一个数a,a和a2可以获得a，所以可以进行这样的构造，对于i，让i2，i4,i8
这样构造可以获得最大值

代码

#include <bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T --){
       int n;
       cin >> n;
       vector<bool> st(n + 1,0);
       for(int i = 1; i <= n; i ++){
           int idx = i;
           while(idx <= n && !st[idx]){
               cout << idx << " ";
               st[idx] = true;
               idx *= 2;
           }
       }
        cout << "\n";
    }

    return 0;
}