北邮oj-非平方不等式

本题暴力枚举很容易想到，但也会超时。
关键在于缩小x的范围。
https://blog.csdn.net/birdstorm_s/article/details/20386413
https://blog.csdn.net/cqhblg/article/details/87258816
这两篇大神的文章讲得很清楚。
由x*x+s(x)*x-n=0推导

xx+s(x)x=n
x(x+s(x))=n
所以x<sqrt(n),x+s(x)>sqrt(n)
因为x<sqrt(n),所以x<10^9
所以s(x)<=99=81
所以sqrt(n)-81<x<sqrt(n)
这就是x的范围

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL s(LL x){//求和函数
	LL result=0;
	while(x!=0){
		result+=x%10;
		x=x/10;
	}
	return result;
}
int main(){
	LL x,n;
	while(scanf("%lld",&n)!=EOF){
	bool flag = false;	//n是long long类型，sqrt(n)也是long long类型，所以下面的x也要是long long类型，不然不能比较，oj提示错误。
	for(LL x=(LL)sqrt(n)-81;x<=(LL)sqrt(n);x++){
		if(x>0&&x*x+s(x)*x==n){//当n较小时，sqrt(n)-81<0，排除这种情况
			printf("%lld\n",x);
			flag = true;
			break;
		}
	}
	
	if(flag==false)
	 printf("-1\n");
	}
	return 0;
}