GGCURR - Editorial

PROBLEM LINK:

Practice
Contest

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.

RELATED PROBLEMS:

There is very big flaw in test cases! Even the tester solution fails to figure out this one! The value of Si goes beyond the range! i.e. it will go up to >100000. please don’t frame such a dumb test cases.

See this one. I used assert to find out bug!

I thank you for pointing out that bug. That was a mistake on my part. The code which I used to generate the test cases is here http://pastebin.com/Up4854bj
As you can see the code on line 27 can generate a value up to 100003 (which is slightly more than what is mentioned).
I will take care of the details next time. Thanks again for giving your time to find the problem.

//