30.md (1764B)
1 Source: https://codeforces.com/blog/entry/696 2 3 # Tutorial for problem "A. Accounting" 4 5 ### First solution: naive brute 6 7 Let's brute all possible values of *X*, and check each of them. It's easy to understand, that *X* will be constrained in the same limits as values *A* and *B*, that is, from -1000 to 1000 inclusive (obviously, there exists a test for each such *X*, so we can't decrease these limits). 8 9 When we have some fixed value of *X*, we check it simply by multiplying *A* by *X* *n* times. But, you should be careful with possible integer (and even 64-bit integer :) ) overflow. For example, you should stop multiplying by *X* if the currect result exceeds 1000 by absolute value already. 10 11 ### Second solution: formula 12 13 It's easy to note, that if solution exists, then it is *n*-th root from |*B*| / |*A*| fraction, with changed sign if *A* and *B* have different signs and if *n* is odd (if *n* is even, then no solution exists). That's why we could just use pow() function (or some analog in your language) to calculate 1 / *n*-th power of the fraction, and after that we just have to check - is the result integer number or not. Of course, we have to check it with taking into account precision errors: that is, number is integer if it is within 10- 9 (or some another number) from nearest integer. 14 15 Moreover, in this solution you should be careful with zeroes. The worst case is when *A* = 0, and this case should be checked manually (you should note the difference between *B* = 0 and *B* ≠ 0 cases). 16 17 It should be told that many of the solutions failed on tests with *A* = 0, or *B* = 0, and if these tests were not included in the pretestset, I think, about half of participants would fail to solve this problem :)