P9345 夕阳西下几时回 题解

一道非常好的数论题

题意

有一个有 n 个元素的环，第 i 个元素的标号为 i，每个元素有一个权值，这个环的总权值为相邻两个元素权值的最大公约数组成序列 b 的不同元素的个数，现在知道元素个数和总权值，让你求出原排列。

证明

已知环内所有元素的权值都小于 n，而且任意两个数（两数不同）的最大公约数都不会大于两个数之间较小的数，显然也不会大于较大的数。如果要让两个数的最大公约数尽量的大,那两个数之间的较小的数也要尽量的大。显然，当环中权值为 n 的元素和权值为 n/2 的元素并列时，两数有最大公约数，而且最大公约数为 n/2，因为 n 为环中最大的数，所以环中最大的最大公约数为 n/2。

进而我们就知道了 k 一定是 \le n/2 的，所以当 k > n/2 的时候，这个序列不可能存在，直接特判就行。

构造序列

先构造一个答案序列，先前环中标号为 x 的元素不变，让他的下一个元素 x+1 的权值 a_{x+1} 变成两倍的 a_x，所以相邻两个数的最大公约数就有价值了。

也就是说让 \le k 的正整数全部存在在答案序列中就完美了。

直接推出原序列。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e5+10;
signed main(){
    int T;
    cin >> T;
    while(T--){
        int n,k;
        cin >> n >> k;
        int vis[maxn];
        vector <int> vec;
        for(int i=0;i<=n+1;i++){
            vis[i]=0;
        }
        if(k>(n/2)){
            cout << "No" << endl;
            continue;
        }else{
            cout << "Yes" << endl;
        }
        for(int i=1;i<=k;i++){
            int ans=i;
            if(vis[i]!=1){
                while(1){
                    vec.push_back(ans);
                    vis[ans]=1;
                    ans=ans*2;
                    if(ans>k){
                        break;
                    }
                }
                vec.push_back(ans);
                vis[ans]=1;
            }
        }
        for(int i=k+1;i<=n;i++){
            if(!vis[i]){
                vec.push_back(i);
            }
        }   
        for(int i=0;i<vec.size();i++){
            cout << vec[i] << " ";
        }
        cout << endl;
    }
    return 0;
} 

提示

因为 T 的范围太大，做了 T 遍 memset，复杂度会达到 O(\max n)，应手动将 vis 标记数组归零。