PROBLEM STATEMENT
Given an integer n, and two non-negative integers a and b where both a and b
are less than n, let:
f(a, b, n) = (a * b) mod n.
In general M mod N is calculated by determining the integer remainder of M when
divided by N for any values M and N. For example 14 divided by 4 has remainder
2, thus, 14 mod 4 = 2.
For example, if n = 5, a = 2, and b = 3,
f(a, b, n) = (2 * 3) mod 5 = 6 mod 5 = 1
However, if n = 4 and b = 2, there is no number a such that:
f(a, b, n) = 1.
Your task is as follows: given the values for b, n and the result, determine
the minimum integer value of a in the range 0 <= a < n such that f(a, b, n) =
result. If there is no such value a, return -1. Also, if b is not in the range
1 <= b < n or result is not in the range 0 <= result < n, there can be no
solution, so return -1.
DEFINITION
Classname: Coefficients
Methodname: findFactors
Parameters: int, int, int
Returns: int
Method signature (be sure your method is public):
int findFactors(int b, int n, int result)
TopCoder will enforce the following input restrictions:
* 1 <= b <= 1000000000
* 2 <= n <= 1000000000
* 0 <= result <= 1000000000
EXAMPLES
Example 1:
b = 3, n = 5, result = 1
We are looking for the smallest a such that f(a, 3, 5) = 1.
The method should return 2, because 2 is the lowest such number a in the range
0 <= a < n that satisifies this condition.
Example 2:
b = 2, n = 4, result = 3
There is no possible integer solution to this, so the method returns -1.
Example 3:
b = 17, n = 80, result = 8
Method returns: 24
Example 4:
b = 123456789, n = 657123782, result = 7
Method returns: 382402181