大佬相助,等式的根

等式的根

有这样一个式子

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

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

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

输入格式:

输入一个整数n。(1≤n≤1018)

输出格式:

输出一个整数

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

样例输入1:

110

样例输出1:

10

样例输入2:

4

样例输出2:

-1

源自XJOI,经典普及;
求大佬相助
好人一身平安!!!

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

unsigned long long n;

void KYC ( )
{
bool flag = false;

for(long long i = sqrt(n); i >= 1; --i)
{
	int sum = 0;
	int b = i; 
	while(b)
	{
		sum += b % 10;	
		b /= 10;
	}
	
	if(i * i + sum * i == n)
	{
		flag = true;
		cout << i;
		break;
	}
}
if(flag == false) cout << -1;

}

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

1 个赞

有无大佬相助!

1 个赞

有,这简单,直接枚举思密达

for(...(这个自己填);i<=sqrt(n);i++){
        x=i;
        s=0;
        while(x>0){
            s+=x%10;
            x/=10;
        }
        if(i*(i+s)==n){
            printf("%lld",i);
            return 0;
        }
    }

咋写啊!!!

1 个赞

不会啊!!!
普及的题!!!

1 个赞

x^2+S(x)x*-n=0,即x(x+S(x))=n,故x<sqrt(n),由于n<=10^18,S(x)必须小于162,x(x+162)>=n,
而x(x+162)<(x+81)^2,则x+81>sqrt(n),从sqrt(n)-81枚举到sqrt(n)即可

1 个赞

谢谢大佬,大恩大德,永生难忘!!!

1 个赞

@张昊泽 最好加改成

i=max((long long)(1),(long long)(sqrt(n)-81))

因为n有可能小于81,你见过sqrt(负数)吗?(也不是没有,只是不好算)
@linan04113 懂?改一下