P13098 构造大师贝贝 题解

· · 题解

1. 题意解释

给出一个数 n，每次你可以选择 n 的一个因数 m，并使 n=n+m 且 m 不可重复，求如何使 n 成为一个完全平方数。

2. 思路

主播赛时切掉了这道抽象的构造题来讲一下心路历程。

最开始时肯定会想到往最近的完全平方数靠。

然而这样我们会发现，有些数字是无法变成与其最接近的完全平方数的。

例子：7。

与 7 最接近的完全平方数是 9，可你会发现没有办法使 7 转化为 9。

主播本来这时候打算放弃了。

然而数竞的经历让主播想到了分类讨论和整除性。

我们考虑对 n 分类讨论。

我们让 n 加上 1（这是显然可行的），此时 n+1 是一个偶数（显然），再让其加上 2，此时变为 n+3，变成一个 4 的倍数。

直接让 n 加上 2（显然可行）变为 n+2，依然化为 4 的倍数。

直接让 n 加上 1（显然可行）变为 n+1，依然化为 4 的倍数。

此时，对于所有 n 都已化为 4 的倍数，我们让 n 除以 4，转化为 n/4。

不难发现这样的操作可以一直持续直到 n 已成为一个完全平方数。

至于操作次数，最坏的情况是 2\log_4n，若 100 次操作用完可以达到 4^{50}，大约是 10^{31}。

而操作过程中 n 的最大值显然为 4^{\left\lfloor\log_4n\right\rfloor+1}，不会超过 10^{18}，因而此方法可行。

3. 代码实现

没什么特别难的地方，直接上主播的 code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,cnt;
vector<int>vec;
void solve(int x,int a){
    if(floor(sqrt(x))*floor(sqrt(x))==x){
        cout<<cnt<<endl;
        for(int i=0;i<vec.size();i++){
            cout<<vec[i]<<" ";
        }
        cout<<endl;
    }
    else{
        if(x%4==1){
            cnt+=2;
            vec.push_back(a);
            vec.push_back(2*a);
            solve((x+3)/4,a*4);
        }
        else if(x%4==2){
            cnt++;
            vec.push_back(2*a);
            solve((x+2)/4,a*4);
        }
        else if(x%4==3){
            cnt++;
            vec.push_back(a);
            solve((x+1)/4,a*4);
        }
        else{
            solve(x/4,a*4);
        }
    }
}
signed main(){
    cin>>t;
    while(t--){
        cin>>n;
        cnt=0;
        vec.clear();
        solve(n,1);
    }
    return 0;
}