Not able to get the editorial

#1

I am doing this question from codeforces…
https://codeforces.com/problemset/problem/633/A
I have solved it using brute force…
https://codeforces.com/contest/633/submission/97974393
But here in editorial … they have talked about some other approch.
I think it is linear diophantine equation… But here we can’t make ‘x’ and ‘y’ of ax+by = c…Negative as we can select a and not…
so i think…only linear diophantine equation won’t work here.
My question is–
What is the editorial talking about…the another approch…
Thanks

#2

Hey @ashishnnnnn
Yes its talking abt linear diophantine eqn
And its also mentioned that solution exist “iff gcd ( a , b )| c . We just have to make one more check to ensure a positive integral solution”

#3

But from linear diophantine equation… It can also possible that the x,y which come… one may be -ve…But here we have two choices either select ‘a’ or neglect it… means x and y of ax+by=c…can only be non-negative

#4

Yes that what editorial is saying that after ensuring this gcd ( a , b )| c
make sure that x and y both are positive

#5

Ooo… And to check that x and y are positive or not… what can be the approch…other than brute force…

#6

I think extended euclid algorithm will be used for that
Using this ax + by = gcd(a, b)
We can find x and y in it and if both are positive then ans is YES

#7

Thanks i Got this :slight_smile:

1 Like
#8

Hii… I have asked so many doubts in the single section… that’s why or may be… this doubt is not showing there. So i am unable to mark it as resolved.

#9

I will mark it ,dont worry about it :slight_smile:

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.