PolynomialRemainder | Topcoder Archive

Problem Statement

Cat Snuke received a polynomial P(x) = ax^2 + bx + c as a present. Now he is interested in finding a nonnegative integer y such that P(y) is divisible by one billion (10^9).

You are given three ints a, b, and c. Find an integer y between 0 and 999,999,999, inclusive, such that P(y) is divisible by one billion. If there are multiple solutions, return any. If there is no solution, return -1 instead.

Definition

Class:: PolynomialRemainder
Method:: findRoot
Parameters:: int, int, int
Returns:: int
Method signature:: int findRoot(int a, int b, int c)
(be sure your method is public)

Constraints

a, b, and c will be between 0 and 999,999,999, inclusive.

Examples

```
0
```
```
0
```
```
0
```
```
Returns: 0
```
P(x) = 0 for all x. Any integer between 0 and 999,999,999, inclusive, will be accepted.
```
0
```
```
0
```
```
1
```
```
Returns: -1
```
P(x) = 1 for all x, so there is no solution.
```
1
```
```
2
```
```
3
```
```
Returns: -1
```
We can prove that there is no solution in this case.
```
123456000
```
```
789012345
```
```
678901230
```
```
Returns: 121618466
```
P(x) = 123456000x^2 + 789012345x + 678901230. P(121618466) = 1826044121818350000000000.

479659453

928595613

143451144

Returns: 647373336

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.