CF1934E

Hanghang · 2024-03-02 09:58:02 · 题解

思路借鉴了 rainboy 大佬，拜谢。

主要记录一下思考过程吧，这题还是比较巧妙的。

首先注意到操作次数的上界大约是 \dfrac{n}{6}，每次操作只能改变 3 个位置的值，中间大概差了两倍。

这成为了突破口，我们大胆猜测每个位置至多操作一次的话，那么将会有一半的位置值不会变。

那这一半左右的位置究竟是哪些呢？

跟一半有关的东西大概有：奇偶，前一半后一半。

这题看样子就跟奇偶没差本质联系，所以从后者开始思考。

首先大胆猜测应该前一半尽量不操作，后一半操作。因为不断操作小的数 x 容易使得无法使得最后没有最大公因数为 x。

那我们可以从 n 往小的数考虑。

如果 n 是奇数，我们可以将 (n-2,n-1,n) 一起操作，这样我们要查询最大公因数为其中某个数的时候选其中的两个数即可。

如果 n 不是 4 的倍数，我们可以操作 (\dfrac{n}{2},n-2,n-1)，原因是，如果我们跟奇数一样操作的话，那么一次操作中就会出现两个偶数，在变成最小公因数的时候就不是简单的相乘了，那么我们在查询最大公因数的时候也就不是想要的值了。而这么操作的原因是 n 质因数分解后只会有一个 2，那么，我们 \operatorname{lcm}(n-2,\dfrac {n}{2}) 后恰好是 n 的倍数，查询的时候将两者一起询问即可构造出最大公因数为 n 的值。n-1,n-2 的值不会被影响，跟奇数类似。\dfrac{n}{2} 这个值其实也不用担心，因为它和 n-1,n-2 互质，那么查询 n-1,n-2 的最大公因数也就能找到 \dfrac{n}{2}。

如果 n 是 4 的倍数，我们可以操作 (\dfrac{n}{2}-1,n-1,n)，原因跟上者类似。

还有些细节就是这么构造可能会剩下不到三个数，有点讨厌。

方法是在一开始的时候操作 (1,n-1,n-2)，这样就解决了。

总而言之就是这种构造需要大胆猜测加上细致分析，还是非常困难的。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e6+3;
void Solve()
{
    ll n,m,k;cin>>n;k=n;m=(n+1)/2;
    cout<<(m+2)/3<<endl;
    if(m%3)cout<<1<<" "<<k-1<<" "<<k<<endl,k-=2;
    for(;k*2>n;k-=3)
    {
        if(k%2)cout<<k-2<<" "<<k-1<<" "<<k<<endl;
        else if(k%4)cout<<k/2<<" "<<k-2<<" "<<k-1<<endl;
        else cout<<k/2-1<<" "<<k-1<<" "<<k<<endl; 
    }
}
int main()
{
    int T;cin>>T;
    while(T--)Solve();
    return 0; 
}