Setter: Harikrishna N
Extended Euclidean Algorithm and Linear Diophantine Equation.
There are two microchips for each robot (A and B). You are given powers of microchips A and B along with the total power C that is required to neutralize a robot. We need to find how many robots can be neutralized.
We can only insert a whole number of microchips.
We can represent the problem in the form of Ax + By = C
Where, A = power of microchip A, B = power of microchip B, C = power required to neutralize the robot.
Therefore, we need to check if there is a positive integer solution for the above equation.
There exists an integer solution for Ax + By = C if and only if C is a multiple of gcd(A, B) (Bezout’s identity).
Condition for an integer solution to exist:
C % gcd(A,B) = 0
Now we need to check if the equation has a positive solution.
For finding the initial solution of the equation Ax + By = gcd(A, B), we need to use the Extended Euclidean Algorithm.
Let (xg, yg) be the solution of Ax + By = gcd(A, B)
For finding initial solution of Ax + By = C, by using (xg, yg) we need to use Linear Diophantine Equation
Let (x0, y0) be the initial solution of the equation Ax + By = C.
From linear Diophantine equation, any general solution can be written as:
- x = x0 + k*(B/g)
- y = y0 - k*(A/g)
Where k is any integer and g is gcd(A, B)
Proof of the above equation
The above general solution gives all possible solutions of Ax + By = C for different values of k. We need to check if there is at least one solution such that x > 0 and y > 0.
- x0 + k*(B/g) > 0
- y0 - k*(A/g) > 0
So from rearranging the above two equations we get,
k > (-x0 * g) / B => L
k < (y0 * g) / A => R
Equation L and R can be considered the range of k (where k is an integer)
If there exist at least one integer between L and R, there is a positive integer solution
O(n * log(n))
import sys def multiple_input(): return map(int, sys.stdin.readline().strip().split()) def list_input(): return list(map(int, sys.stdin.readline().strip().split())) def initial_solution(a, b): if a % b == 0: return [0, 1, b] x, y, gcd = initial_solution(b, a % b) return [y, x - (a // b) * y, gcd] for _ in range(int(input())): n = int(input()) count = 0 for i in range(n): a, b, c = multiple_input() xg, yg, g = initial_solution(a, b) # if c is not multiple of gcd(A, B), then solution does not exist. if c % g != 0: continue else: # initial solution of Ax + By = C x0, y0 = xg * (c // g), yg * (c // g) y = (y0 * g) / a x = (-x0 * g) / b if y - x > 1: count += 1 elif y - x == 1: if y // 1 != y: count += 1 elif 0 < y - x < 1: if y != y // 1 and x != x // 1: if y // 1 != x // 1: count += 1 print(count)