CF1934E 题解

· · 题解

\textbf{CF1934E *3000}
  • 给定长度为 n 的序列 a，初始时满足 a_i=i。一次操作为选择三个互不相同的下标 i,j,k，设 x=a_i,y=a_j,z=a_k，令 a_i = \operatorname{lcm}(y,z),a_j = \operatorname{lcm}(x,z),a_k = \operatorname{lcm}(x,y)。
  • 在 \lfloor \dfrac{n}{6} \rfloor +5 次操作内，将序列 a 变成好的。好的序列指的是，对于任意 x \in [1,n]，都存在 a 的一个长度至少为 2 的子序列 a'，使得 \gcd\{a'\} = x。

对这种 ad-hoc 构造真没一点思路，做法参考了官方题解。

不妨令 d = \gcd(x,y,z),x=ad,y=bd,z=cd，则 a,b,c 应当两两互质。那么操作完后，三元组 (x,y,z) 将变为 (bc \cdot d,ac \cdot d,ab \cdot d)，两两组成子序列即可得到 \gcd 为 x,y,z 的子序列。

这样一来，如果我们能把序列 a 分成若干个满足上述条件的三元组，对其分别操作后序列 a 将满足条件，需要 \dfrac{n}{3}+\mathcal O(1) 次操作。

显然序列中一定存在元素 2i 的倍数 k \cdot 2i，那么子序列 \{i,k \cdot 2i\} 的 \gcd 为 i，已经满足要求。

这样我们的操作次数降到 \dfrac{n}{6}+\mathcal O(1) 次，可以满足条件。接下来考虑如何划分。

  • 对于 x \bmod 4=3，(x,x+1,x+2),(x+4,x+5,x+6),(x+8,x+9,x+10) 的结构都是 (2k-1,2k,2k+1)，满足条件。(x+3,x+7,x+11) 的结构是 (4k+2,4k+6,4k+10)，除以 2 后变为 (2k+1,2k+3,2k+5)，两个奇数 x,y 满足 |x-y| \le 4 一定互质，那么 (2k+1,2k+3,2k+5) 满足条件。
  • 对于 x \bmod 4 = 2，(x+1,x+2,x+3),(x+5,x+6,x+7),(x+9,x+10,x+11) 的结构是 (2k-1,2k,2k+1)，而 (x,x+4,x+8) 的结构是 (4k+2,4k+6,4k+10)，满足要求。

注意到如果 n \bmod 4 = 1 或 2，我们直接选择 [n-11,n-10,\ldots,n-1,n] 就是一个满足 x \bmod 4 \ge 2 的段，将 n \gets n-12 后继续操作即可。当 n \bmod 4 = 0 或 3 时，我们执行操作 (1,n-1,n-2)，即可转化为上述情况。

总操作次数 \dfrac{n}{6}+1，满足要求。

有个细节是当 n \le 12 时不存在满足条件的长度为 12 的连续段，这个时候我们需要爆搜或者手玩寻找答案。

下面的代码中 n \le 12 的情况复制自官方题解。

/**
 *    author: sunkuangzheng
 *    created: 02.03.2024 10:07:11
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T,n; vector<tuple<int,int,int>> pans[15];
void los(){
    cin >> n;
    vector<tuple<int,int,int>> ans;
    pans[3]={{1,2,3}};
    pans[4]={{1,3,4}};
    pans[5]={{3,4,5}};
    pans[6]={{1,3,5},{2,4,6}};
    pans[7]={{2,4,6},{3,5,7}};
    pans[8]={{2,6,8},{3,5,7}};
    pans[9]={{1,3,5},{2,4,6},{7,8,9}};
    pans[10]={{3,4,5},{2,6,8},{7,9,10}};
    pans[11]={{2,6,8},{3,5,7},{9,10,11}};
    pans[12]={{1,11,12},{6,8,10},{5,7,9}};
    auto add = [&](int x,int y,int z){ans.emplace_back(x,y,z);};
    if(n <= 12) ans = pans[n];
    else{
        if(n % 4 == 0 || n % 4 == 3) add(1,n-1,n),n -= 2;
        int rn = n / 2;
        while(n > rn){
            int d = n - 11; 
            if(d % 4 == 3) add(d,d+1,d+2),add(d+4,d+5,d+6),add(d+8,d+9,d+10),add(d+3,d+7,d+11);
            else add(d+1,d+2,d+3),add(d+5,d+6,d+7),add(d+9,d+10,d+11),add(d,d+4,d+8);
            n -= 12; 
        }
    }cout << ans.size() << "\n";
    for(auto [x,y,z] : ans) cout << x << " " << y << " " << z << "\n";
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}