233B.md (1375B)
1 Source: https://codeforces.com/problemset/problem/233/B 2 3 B. Non-square Equation 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Let's consider equation: 22 23 *x*2 + *s*(*x*)·*x* - *n* = 0, 24 25 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. 26 27 You are given an integer *n*, find the smallest positive integer root of equation *x*, or else determine that there are no such roots. 28 29 Input 30 31 A single line contains integer *n* (1 ≤ *n* ≤ 1018) — the equation parameter. 32 33 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. 34 35 Output 36 37 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. 38 39 Examples 40 41 Input 42 43 ``` 44 2 45 ``` 46 47 Output 48 49 ``` 50 1 51 ``` 52 53 Input 54 55 ``` 56 110 57 ``` 58 59 Output 60 61 ``` 62 10 63 ``` 64 65 Input 66 67 ``` 68 4 69 ``` 70 71 Output 72 73 ``` 74 -1 75 ``` 76 77 Note 78 79 In the first test case *x* = 1 is the minimum root. As *s*(1) = 1 and 12 + 1·1 - 2 = 0. 80 81 In the second test case *x* = 10 is the minimum root. As *s*(10) = 1 + 0 = 1 and 102 + 1·10 - 110 = 0. 82 83 In the third test case the equation has no roots.