我的经历

我因为懒得根据数论来做，然后就随手打了个 dfs 暴力枚举，然后我觉得应该过不了（这种题一看就不是 dfs 的料）。我抱着试试的态度交了上去，发现 $30$ 分，但是剩下的不是全都超时！有一个点是 WA 。。。

然后我把题面往下划，看了一眼数据范围，$1 \le n \le 10^{12}$ 。。。那得开 long long 啊。。。

回到代码，改成 long long ，又交了一遍，发现还是 $30$ 分，剩下的全超时了。

我的超时记录

我当时是这么写的：

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

long long n;

bool isPerfectSquare(long long x){
	for(long long i=1;i<=n;i++){
		if(i*i==x){
			return true;
			break;
		}
	}
	return false;
}

void dfs(long long x){
	if(isPerfectSquare(n*x)){
		cout <<x<<endl;
		return;
	}
	dfs(x+1);
}

int main(){
	cin >>n;
	dfs(1);	
	return 0;
}

但是我这是练习，所以我还是写了一下数学做法，最后过了。

我的感想

如果是数论题还不是特别难，那就不要浪费时间去写暴力了，反正也过不了。

还有就是一定要在写完后分析复杂度并且仔细想想还能不能优化，如果能优化，那一定要优化！

最后，一定要看清数据范围，像本题 $1 \le n \le 10^{12}$ 的，就会炸 int ，所以要开 long long ！最后引用一句话：十年 OI 一场空，不开 long long 见祖宗！