PolynomialRemainder
SRM 657 · 2015-03-26 · by rng_58
SRM 657 · 2015-03-26 · by rng_58 · Brute Force, Math
Problem Statement
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.
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.
Constraints
- a, b, and c will be between 0 and 999,999,999, inclusive.
Examples
0)
0 0 0 Returns: 0
P(x) = 0 for all x. Any integer between 0 and 999,999,999, inclusive, will be accepted.
1)
0 0 1 Returns: -1
P(x) = 1 for all x, so there is no solution.
2)
1 2 3 Returns: -1
We can prove that there is no solution in this case.
3)
123456000 789012345 678901230 Returns: 121618466
P(x) = 123456000x^2 + 789012345x + 678901230. P(121618466) = 1826044121818350000000000.
4)
479659453 928595613 143451144 Returns: 647373336
Submissions are judged against all 127 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PolynomialRemainder with a public method int findRoot(int a, int b, int c) · 127 test cases · 2 s / 256 MB per case