You are given * N , A , B* find such x and y that

**(A*x + B*y) = N**and

**x>=0 , y>=0**. It is not guaranteed that N will be always gcd(a,b) .

If such x , y does not exist print -1 , either print x and y in same line separated by space , if there are multiple x , y that satisfy the equation print any of them .

**For example:** If N=9 , A=2 , B=5

then ans is 2 1 . Because 2*2+5*1=9 . Here A=2 , x=2 and B=5 , y=1 .

**Constraint:**

1<= N , A , B <= 10^18

**INPUT**

9 2 5

22 3 7

439365 78717 87873

505383 77277 99291

1000000 3 999997

474441 99291 77277

911106 51038 78188

321361 79845 81826

1000000000000000000 8765433 54343345

**OUTPUT**

2 1

5 1

0 5

-1

1 1

4 1

1 11

3 1

25359400 18397426840

I have solved using linear loop .

for(long long i=0; i<=n/a; i++) if((n-i*a)%b==0) { printf("%lld %lld\n",i,(n-i*a)/b); return 0; } printf("-1\n");

But constraint is so big so this would not pass . For this test case n=1000000000000000000 , a=3 , b=798877665 code is getting TLE .

How to solve this problem efficiently ? This is a subproblem of this problem http://codeforces.com/contest/932/problem/C

**UPD solved it using extended euclid here is the code** : https://ideone.com/6fzPLF

There is an algorithm named Extended Euclidean algorithm. It runs on logarithmic time.

But extended euclidian algorithm will work only for A*x+B*y=GCD(A,B) , that means right hand value of above equation must have to be equal to the GCD(A,B) . But i mentioned in the problem that it is not guaranteed that right hand side will be equals to gcd(A,B) .

In the Above problem A*x+B*y=N , if N!= GCD(A,B) then it is not possible to apply extended euclidian algorithm . How to solve it then ?

multiply x and y with N/gcd(A,B)

Can you please elaborate it .

OK. basically it is simple math. We can calculate u, v which meets Au+Bv = gcd(A, B) with Ext Euclidean Algorithm.

we multiply both side with N/gcd(A, B) if N is divisble by gcd(A, B)

It gives A(Nu/gcd(A,B)) + B(Nv/gcd(A, B)) = N.

Then your x is Nu/gcd(A, B) and y is Nv/gcd(A, B)

If N is not divisible by gcd(A,B) then ?

What do you expect?

Your above equation A(Nu/gcd(A,B)) + B(Nv/gcd(A, B)) = N . can be rewritten as ,

u*(N*A/gcd(A,B)) + v*(N*B/gcd(A, B)) = N

=> u * A' + v* B' = N

Here A'= N*A/gcd(A,B) , B'=N*B/gcd(A, B)

If N is divisible by gcd(A,B) then it is sure that gcd(A' , B' ) = N but if not then

gcd(A' , B' ) != N . This is my expectation

if N is not divisible by gcd(A,B) there is no such integer x and y because left hand side is always divisible by gcd(A, B)

Thank you i got my answer . :)

I have a question , please answer . In extended euclidian algorithm for any A*x + B*y = GCD(A,B) ,

if(A!=B){

x or y one of them will be negative . If x is negative then y is positive , if y is negative x is positive .

Is this true ?}

My blog post problem was find x,y such that x>=0 , y>=0 and A*x + B*y = N . Therefore euclidian algorithm gives x or y negative so this does not satisfy the constraint . So i think it is impossible to solve this problem with x>=0 , y>=0 and A*x + B*y = N .

Am i right ? If wrong please correct me . Sorry for my poor englishyes, and you can use the fact that A(x+B) + B(y-A) = Ax+By to adjust the numbers

So it is

impossibleto solve this problem with x>=0 , y>=0 and A*x + B*y = N ?please answerI didn't get you , what do you mean by adjust numbers

If (x, y) = (u, v) is one solution of Ax+By=N, actually you are getting infinitely many solution (x,y) =(u+t(B/g), v-t(A/g)) where t is any integer and g is gcd(A, B)

pick one with both two numbers are positive.

please answer , i am sorry for annoying you , this is my last questionto get positive pair and put the value of t . I have to use for loop , is there any limitation of t that i will get positive pair atleast there ? Or use an infinite loop ?

Consider range of t that would bring both x and y non-negative. You can get it in O(1) time.

how can it be without loop ? Only O(1) ? :O . What's the formula ?

solve the inequality x>=0 and y>=0 for t where (x, y) = (u+t(B/g), v-t(A/g)) (with your pencil and paper) and check whether integer is inside of the range or not.

Your idea is not giving correct output . I am not saying you are wrong but why this does not

if n=9, a=2 , b=5 . Then 2*x+5*y=9

2*x + 5*y = gcd(2,5)

=>(2*x*9)/gcd(2,5) + (5*y*9)/gcd(2,5) = gcd(2,5)*9 / gcd(2,5) [ dividing both side with 9/gcd(2,5) ]

=> 2*x*9 + 5*y*9 = 9

=> 18*x + 45*y = 9

now a=18 , b=45 . Now using extended euclid we get x=-2 , y=1 . Since x and y have to be positive . So i will use the formula

(x,y) = ( x+t*b/gcd(a,b) , y-k*a/gcd(a,b) ) ;x+ t*b/gcd(a,b) >=0 will be true if and only if t>=( -x * gcd(a,b) /b ) ;

so putting the value ,

t>=( -x * gcd(a,b) /b )

t>=( -(-2) * 9/45 )

t>= 18/45

y- k*a/gcd(a,b) >=0 will be true if and only if t<=( y*gcd(a,b)/a ) ; putting the value

t<=( y*gcd(a,b)/a )

t<= 1* 9/18

t<= 9/18

so inequalityes are t>= 18/45 && t<= 9/18 . If i put t=18/45 then it satisfy the inequalities .

Since

(x,y) = ( x+t*b/gcd(a,b) , y-k*a/gcd(a,b) ) ;so x= x+t*b/gcd(a,b) ;

=> x= -2+ (18*45)/(9*45)

=> x= -2 + 2

=> x=0

and y= y-k*a/gcd(a,b)

=> y= 1- (18*18)/(9*45)

=> y= 1-0.8

=> y=0.2

We finally got x=0 , y=0.2 . But it is not 2*0 + 5 * 0.2 != 9 which does not satisfy a*x + b*y = n

Here's the correct step.

Start with 2

x+ 5y= 9. Since (2, 5) = 1, we will begin with solving 2x' + 5y' = 1.Extended Euclid will give you

x' = - 2 andy' = 1 will work, so takingx= 9x' andy= 9y', we will havex= - 18 andy= 9. Sox= - 18 + 5tandy= - 2t+ 9 will work.To get

x,y> 0, we solve the ineq fortand just chooset= 4, givingx= 2 andy= 1.How does these equation come from ? please answer

x = - 18 + 5t , y = - 2t + 9 ?

UPD : i understood it comes from the formula x=x+t*b/gcd(a,b)

Finally solved it , implemented your idea . And it successfully give the correct result . Thanks for your help . Thanks everyone .

https://ideone.com/6fzPLF

But, in that problem N = 1e6 right ?

yes .

you can try something like this:

`

If n equals 10^18 and answer is -1 , then the loop will continue up to 10^18 which is not efficient solution ,