daihan's blog

By daihan, 6 years ago, In English

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

  • Vote: I like it
  • -15
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it -14 Vote: I do not like it

    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 ?

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

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

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        Can you please elaborate it .

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +18 Vote: I do not like 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)

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it -11 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it +12 Vote: I do not like it

              What do you expect?

              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it +11 Vote: I do not like it

                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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

                  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)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

                  Thank you i got my answer . :)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it -18 Vote: I do not like it

                  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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  yes, and you can use the fact that A(x+B) + B(y-A) = Ax+By to adjust the numbers

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                  Rev. 5   Vote: I like it -10 Vote: I do not like it

                  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;
                  
                   }
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                  Rev. 2   Vote: I like it +10 Vote: I do not like it

                  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.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

But, in that problem N = 1e6 right ?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
        }
    }

`

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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