Problem Non-square Equation

Link: http://codeforces.com/problemset/problem/233/B

B. Non-square Equation

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Let's consider equation:

x² + s(x)·x - n = 0, 

where x, n are positive integers, s(x) is the function, equal to the sum of digits of number x in the decimal number system.

You are given an integer n, find the smallest positive integer root of equation x, or else determine that there are no such roots.

Input

A single line contains integer n (1 ≤ n ≤ 10¹⁸) — the equation parameter.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin,cout streams or the %I64d specifier.

Output

Print -1, if the equation doesn't have integer positive roots. Otherwise print such smallest integer x (x > 0), that the equation given in the statement holds.

Sample test(s)

input

2

output

1

input

110

output

10

input

4

output

-1

Note

In the first test case x = 1 is the minimum root. As s(1) = 1 and 1² + 1·1 - 2 = 0.

In the second test case x = 10 is the minimum root. As s(10) = 1 + 0 = 1 and 10² + 1·10 - 110 = 0.

In the third test case the equation has no roots.

Bài toán trên rất đơn giản:
- tổng các chữ số của một số từ 1 - 162(9*18): 000000000000000001...999999999999999999. 

- Lặp với tổng các chữ số: tính delta để có nghiệm nguyên thì delta là một số chính phương, do đó viết một hàm kiểm tra số chính phương.

- Nghiệm là số dạng (-s(x)+sqrt(delta))/2 do đó -s(x)+sqrt(delta) phải chia hết cho hai.

- Viết hàm tính Sum(x): tổng các chữ số của x . Kiểm tra xem có bằng tổng s không.

Code:

#include<iostream>

#include<cmath>

using namespace std;

bool IsRoot(long double x);

int Sum(long long t);

int main()

{

//cout << Sum(101);

long long N;

cin >> N;

for(int s = 1; s <= 162; s++)

{

long double delta = (long double) (s*s+4*N);

if(!IsRoot(delta)) continue;

long double xx = sqrt(delta);

if(((long long)(xx-s)%2)==1) continue;

long long t = (long long)((xx-s)/2);

if(Sum(t) == s)

{

//cout << "delta=" << delta << endl;

//cout << "s=" << s << endl;

//cout << "xx=" << xx << endl;

cout << t << endl;

//system("pause");

return 0;

}

}

cout << -1 << endl;

// system("pause");

return 0;

}

bool IsRoot(long double x)

{

long double xx = (long long)sqrt(x);

// cout << "xx=" << xx << endl;

if(abs(xx*xx-x)<0.00001) return true;

return false;

}

int Sum(long long t)

{

int s = 0;

while(t) 

{

s+=(t%10);

t/=10;

}

return s;

}