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.me/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 english
yes, and you can use the fact that A(x+B) + B(y-A) = Ax+By to adjust the numbers
So it is impossible to solve this problem with x>=0 , y>=0 and A*x + B*y = N ? please answer
I 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 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; }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 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.
But, in that problem N = 1e6 right ?
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 ,