codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.