首页 / 软件开发 / 数据结构与算法 / CodeForces 233B Non-square Equation

CodeForces 233B Non-square Equation2014-12-02链接：

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:

x2+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≤1018） — 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 %I64dspecifier.
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 12+1·1-2=0.

In the second test case x=10 is the minimum root. As s（10）=1+0=1 and 102+1·10-110=0.

In the third test case the equation has no roots.

分析与总结:

之前很少做数学题，所以一看到就想用二分法做，但是一直WA在test 5，后来经提醒可以将公式变形，瞬间明朗。

把公式x2+s（x）·x-n=0, 进行变形：

S（x） = n/x - x。

可大致估计S（x）的范围在1～100之间， 然后枚举S（x）的值，根据S（x）的值和方程S（x） = n/x - x，解出x = sqrt（ S（x）^2/4 + n ）.

然后把x代入原公式x2+s（x）·x-n=0 看是否符合。

代码：

#include<iostream>#include<cstdio>#include<cmath>using namespace std;typedef long long int64;int64 n, sx;int64 digitSum（int64 n）{int64 sum=0;while（n）{sum += n%10;n/=10;}return sum;}int main（）{while（cin >> n）{int64 x=1, end=1e8, ans=-1;for（int64 i=1; i<=100; ++i）{int64 tmp = i*i/4+n;x = sqrt（tmp）-i/2; sx = digitSum（x）;if（x*x+sx*x-n==0）{ans=x;break;}}cout << ans << endl;}return 0;}

作者：csdn博客 shuangde800