Problem - Problem - A - Codeforces
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”
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
1 Like
ok so there is no other way around rather than bruteforce.
Thank you bhaiyya
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
1 Like