### PROBLEM LINK:

**Author:** Suraj Kumar

**Tester:** Rishabh Gupta

**Editorialist:** Suraj Kumar

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

Maths, Linear Diophantine Equation

### PROBLEM:

You are given three integers A,B and S. You just need to tell

whether Ax+By=S has integral solutions such that x>0 and y>0.

You need to do this N number of times for each of the T testcases.

### QUICK EXPLANATION:

We can think of the problem as finding whether a positive solution

exist for the given Linear Diophantine Equation or not.

This can be done by using the Extende eucledian algorithm to

find any particular solution for the given equation and then use

it to check for any available positive solution.

### EXPLANATION:

First use the Extendeg Eucledian Algorithm to find x0 and y0

such that a*x0+b*y0=gcd(a,b).

Now we need to check whether S is a multiple of gcd(a,b) or not.

If not then we will never be able to get integral

solutions for the said equation.

But if it is a multiple of gcd(a,b) then the equation have integral

solutions, so now we need to figure out if there is any positive

integral solutions for the equation.

The can be done by using the method described here.

### ALTERNATIVE SOLUTION:

Simply iterating for the possible values of A and B can also

tell whether the sum can be generated or not.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.