D题求救‎‎

[凌浩诚 (人老，心不老)]

TLE了

D. 等式的根

Problem ID: 1241

Contest ID: 5885

必做题

Time Limit Exceeded

24 分

时间：1s 空间：32M

题目描述：

有这样一个式子

x2+S(x)∗x−n=0

x,n都是正整数, S(x)为x所有十进制数位的和

现在给你一个n，你需要找到最小的x使得等式成立。

输入格式：

输入一个整数n

输出格式：

输出一个整数

如果不存在一个整数使得等式成立，输出-1

样例输入1：

110

样例输出1：

10

样例输入2：

4

样例输出2：

-1

约定：

1<=n<=1018

提示：

一下是我的代码

#include <iostream>
using namespace std;

int f(int x)
{
	int ans(0);
	while (x)
	{
		ans+=(x%10);
		x/=10;
	}
	return ans;
}
int g(int x)
{
	return x*x;
}
int main()
{
	long long n;
	cin>>n;
	int x=1;
	while (g(x)+f(x)*x-n)
	{
		if(x>n) 
		{
			cout<<"-1";
			return 0;
		}
		x++;
	}
	cout<<x;
	return 0;
} 

[屠轩铭 (一只pop猫)]

我也不会

[凌浩诚 (人老，心不老)]

‪‪‪‪‪‪‪‪‪‪‪‪‪‪‪‪

[茅峻溢 (Asriel?)]

思路详见注释

#include<bits/stdc++.h>
using namespace std;
long long n,x;
long long ans;
long long s,op;
int main(){
	cin >> n;//输入部分 
	for(long long i = max((long long)1, (long long)sqrt(n) - 81); i <= sqrt(n); i++){//int不能和long long直接比，要转化。sqrt减少时间复杂度 
		x = i;
		s = 0;//计数器
		while(x != 0){//求个各个位数的和 
			s = s + x % 10;
			x /= 10; 
		}
		ans = i * i + s * i - n;//求差值 
		if (ans == 0){//特判，如果为0，说明成立 
			op = 1;//操作数 
			cout << i;//输出答案 
			break;
		}
	}
	if(op == 0){//如果闭区间内没有，op未被赋值为1，输出-1 
		cout << "-1" ;
	}
	return 0;//结束 
}

[凌浩诚 (人老，心不老)]

谢谢

[方悦丞 (初音ミク)]

x的所有位数均为9时,S(x)<=189
n=x(x+S(x))
因为S(x)>0，则x<x+S(x),x<sqrt(n) 且 x+S(x)>sqrt(n)
x<sqrt(n)且n<=10^18,所以x<=10^9且S(x)<9*9

我没有在水贴

[陈柏衡]