Help required to solve this using Euclidean Algo

Problem - https://codeforces.com/contest/633/problem/A

I first wrote a solution that iff gcd(a,b)|c then answer exists, but realized that we need to have non negative integral solution.
So i checked the editorial. It mentioned this:

Editorial : The problem is to find if there exists a solution to the equation: ax + by = c where x and y are both positive integers. The limits are small enough to try all values of x and correspondingly try if such a y exists. The question can also be solved more efficiently using the fact that an integral solution to this problem exists iff gcd ( a , b )| c . We just have to make one more check to ensure a positive integral solution.

Now my question how can i make this check to ensure a positive integral solution?

1 Like

1)If c % gcd(a,b)=0 , a solution exists.

2)Else “No” :slight_smile:

3—> If solution exists, run a loop from x=0 to x=10000 ,

Inside the loop , value of y= (c-a.x)/b

If y>=0 and x>=0 and if both are integers, you break the loop because you got the required values of x and y

Now, a question may arise, what if I never find any 2 values satifying the above 2 conditions ?

Then the answer is simple:- There exists a solution in which either x or y(or both) is(are) negative, but it is of no use to us so we output No :slight_smile:

1 Like

ok so there is no other way around rather than bruteforce.
Thank you bhaiyya :slight_smile:

1 Like

Always remember this:- “At many places brute-force works like magic and we don’t even realize .Many times brute-force fits into the time-limits as well, for example:- DESTCELL problem, but we fail to recognize and dump the brute-force idea”

Always welcome :slight_smile:

1 Like