Intel OA Arithmetic Expression
Question Details
Bob is a studious boy. He is very interested in solving difficult mathematical problems in no time. By seeing his talent, Bob\'s teacher gave him a problem and asked him...
Full Details
Bob is a studious boy. He is very interested in solving difficult mathematical problems in no time. By seeing his talent, Bob\'s teacher gave him a problem and asked him to solve it as soon as possible.
The problem was, Bob has been given an arithmetic expression A, the integer P, and M and he has to find the smallest non-negative value of x in expression A such that the remainder of dividing A by M equals P. Consider that solution do exist for the problems provided to him. Therefore, if the principles of distribution are applied to expression A (Formally, the expression A is a polynomial of the first degree in variable x).
Can you help Bob with a program to solve the problem in a minimum amount of time.
Input Format:
The first line of input contains the expression A.
The second line of input contains two integers P i M.
The arithmetic expression A will only consist of characters , -, , (, ), x, and digits from 0 to 9. The brackets will always be paired, the operators , - and will always be applied to exactly two values (there will not be an expression (-5) or (4 -5)) and all multiplications will be explicit (there will not be an expression 4(5) or 2(x)).
Output Format:
The first and only line of output must contain the smallest non-negative value of variable x.
Constraints:
i. A (1 \u2264 |A| \u2264 105)
ii. P (0 \u2264 P \u2264 M \u2212 1) i M (1 \u2264 M \u2264 106)
Sample Input 1:
4+x+2
8 9
Sample Output 1:
2
Explanation 1:
Arithmetic expression, A: 4+x+2
P: 8 M: 9
Here, by solving the given equation, we will get:
If x = 0, then the remainder of dividing 4 x 2 with 9 is 6, which is not equal to P.
If x = 1, then the remainder of division 4 x 2 with 9 is 7, which is not equal to P.
If x = 2, then the remainder of division 4 x 2 with 9 is 8, which is equal to P.
Hence, as an output, it will print 2 as the smallest value of variable x.
Sample Input 2:
2(x+(x+3)9)
2 6
Sample Output 2:*
1
Explanation 2:
Arithmetic expression, A: 2(x+(x+3)9)
P: 2 M: 6
Here, by solving the given equation, we will get:
If x = 0, then the remainder of dividing 2 ( x+( x+3 ) 9 ) with 6 is 0, which is not
equal to P.
If x = 1, then the remainder of division 2 ( x+(x+3) 9 ) with 6 is 2, which is equal to P.
Hence, as an output, it will print 1 as the smallest value of variable x.