 Setter: Harikrishna N

Medium

# PREREQUISITES:

Extended Euclidean Algorithm and Linear Diophantine Equation.

# Problem

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.

Observations:

1. We can only insert a whole number of microchips.

2. 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.

# Explanation

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:

1. x = x0 + k*(B/g)
2. 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.
Therefore,

1. x0 + k*(B/g) > 0
2. 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

Time Complexity:
O(n * log(n))

Setter's Solution
``````import sys

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)
``````
1 Like