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 ax0+by0=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.