Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### daihan's blog

By daihan, 10 months ago, ,

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

•
• -15
•

 » 10 months ago, # |   +28 There is an algorithm named Extended Euclidean algorithm. It runs on logarithmic time.
•  » » 10 months ago, # ^ | ← Rev. 2 →   -14 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 ?
•  » » » 10 months ago, # ^ |   +18 multiply x and y with N/gcd(A,B)
•  » » » » 10 months ago, # ^ |   -8 Can you please elaborate it .
•  » » » » » 10 months ago, # ^ |   +18 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)
•  » » » » » » 10 months ago, # ^ |   -11 If N is not divisible by gcd(A,B) then ?
•  » » » » » » » 10 months ago, # ^ |   +12 What do you expect?
•  » » » » » » » » 10 months ago, # ^ |   +11 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' = NHere 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
•  » » » » » » » » » 10 months ago, # ^ |   +3 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)
•  » » » » » » » » » 10 months ago, # ^ |   +8 Thank you i got my answer . :)
•  » » » » » » » » » 10 months ago, # ^ |   -18 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 english
•  » » » » » » » » » 10 months ago, # ^ |   0 yes, and you can use the fact that A(x+B) + B(y-A) = Ax+By to adjust the numbers
•  » » » » » » » » » 10 months ago, # ^ | ← Rev. 2 →   0 So it is impossible to 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
•  » » » » » » » » » 10 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » » » 10 months ago, # ^ | ← Rev. 5 →   -10 please answer , i am sorry for annoying you , this is my last question to 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 ? for(int t=0; ; t++) { ans1=u+t*(B/g); ans2=v-t*(A/g); if(ans1>=0 && ans2>=0) break; }
•  » » » » » » » » » 10 months ago, # ^ |   0 Consider range of t that would bring both x and y non-negative. You can get it in O(1) time.
•  » » » » » » » » » 10 months ago, # ^ |   0 how can it be without loop ? Only O(1) ? :O . What's the formula ?
•  » » » » » » » » » 10 months ago, # ^ | ← Rev. 2 →   +10 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.
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 Your idea is not giving correct output . I am not saying you are wrong but why this does notif n=9, a=2 , b=5 . Then 2*x+5*y=92*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 = 9now 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/45y- k*a/gcd(a,b) >=0 will be true if and only if t<=( y*gcd(a,b)/a ) ; putting the valuet<=( y*gcd(a,b)/a )t<= 1* 9/18t<= 9/18so 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=0and y= y-k*a/gcd(a,b)=> y= 1- (18*18)/(9*45)=> y= 1-0.8=> y=0.2We 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
•  » » » 10 months ago, # ^ |   0 Here's the correct step.Start with 2x + 5y = 9. Since (2, 5) = 1, we will begin with solving 2x' + 5y' = 1. Extended Euclid will give you x' =  - 2 and y' = 1 will work, so taking x = 9x' and y = 9y', we will have x =  - 18 and y = 9. So x =  - 18 + 5t and y =  - 2t + 9 will work.To get x, y > 0, we solve the ineq for t and just choose t = 4, giving x = 2 and y = 1.
•  » » » » 10 months ago, # ^ | ← Rev. 3 →   0 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)
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 Finally solved it , implemented your idea . And it successfully give the correct result . Thanks for your help . Thanks everyone .https://ideone.com/6fzPLF
 » 10 months ago, # |   +5 But, in that problem N = 1e6 right ?
•  » » 10 months ago, # ^ |   0 yes .
 » 10 months ago, # |   0 you can try something like this:  for(int i=0;i<=n;i++) { if(a*i<=n&&(n-a*i)%b==0) { flag=1; counta=i; countb=(n-a*i)/b; break; } } 
•  » » 10 months ago, # ^ |   +1 If n equals 10^18 and answer is -1 , then the loop will continue up to 10^18 which is not efficient solution ,