P13098 构造大师贝贝题解

1. 题意解释

给出一个数

n

，每次你可以选择

n

的一个因数

m

，并使

n=n+m

且

m

不可重复，求如何使

n

成为一个完全平方数。

2. 思路

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

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

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

例子：

7

。

与

7

最接近的完全平方数是

9

，可你会发现没有办法使

7

转化为

9

。

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

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

我们考虑对

n

分类讨论。

$n\equiv1\pmod4$

我们让

n

加上

1

（这是显然可行的），此时

n+1

是一个偶数（显然），再让其加上

2

，此时变为

n+3

，变成一个

4

的倍数。

$n\equiv2\pmod4$

直接让

n

加上

2

（显然可行）变为

n+2

，依然化为

4

的倍数。

$n\equiv3\pmod4$

直接让

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：

CPP

#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;
}

P13098 构造大师贝贝题解

文章操作

1. 题意解释

2. 思路

3. 代码实现

相关推荐

评论

P13098 构造大师贝贝题解