/*----------------------------------------------------------------------+
|      Title:   LongPair.java                                           |
|                                                                       |
|      Author:  David E. Joyce                                          |
|           Department of Mathematics and Computer Science              |
|           Clark University                                            |
|           Worcester, MA 01610-1477                                    |
|           U.S.A.                                                      |
|                                                                       |
|           http://aleph0.clarku.edu/~djoyce/                           |
|           djoyce@clarku.edu                                           |
|                                                                       |
|      Date:   Feb, 2006.                                               |
+----------------------------------------------------------------------*/

public class LongPair {
  
  private long a, b;  // the pair of longs
  
  public LongPair(long aIn, long bIn) { a = aIn; b = bIn; }
  
  public LongPair() { a = 0; b = 0; }
  
  public long getFirst() { return a; }
  
  public long getSecond() { return b; }
  
  public void setFirst(long aIn) { a = aIn; }
  
  public void setSecond(long bIn) { b = bIn; }
  
  // Compute the greatest common divisor of to integers r and s.
  // Either may be positive, negative, or zero.  For negative numbers,
  // the GCD is that if their absolute values, that is, 
  //      GCD(r,s) = GCD(|r|,|s|).
  // For zero,  GCD(r,0) = r, and  GCD(0,0) = 0.
  // The Euclidean algorithm is used to compute the GCD.
  public static long GCD(long r, long s) {
    if (r == 0) return s;
    if (s == 0) return r;
    if (r < 0)  r = -r;
    if (s < 0)  s = -s;
    if (r > s)  return GCD(r%s,s);
    else        return GCD(r,s%r);
  } // GCD
  
  // Compute the least common multiple of two integers
  public static long LCM(long r, long s) { 
    if (r == 0 || s == 0) return 0;
    return (r/GCD(r,s))*s ; 
  } // LCM
  
  // Return the greatest common divisor of the pair of numbers
  public long GCD() { return GCD(a,b); }
  
  // Return the least common multiple of the pair of numbers
  public long LCM() { return LCM(a,b); }
  
  // Find a solution to the linear Diophantine equation
  //     ax + by = c
  // If GCD(a,b) does not divide c, then an ArithmeticException is thrown
  public static LongPair linearDiophantine(long a, long b, long c) 
    throws ArithmeticException
  { 
    if (c == 0) {        // then a solution to  ax + by = 0  is  x = 0, y = 0.
      return new LongPair(0,0);
    } else if (a == 0) { // then a solution to  0x + by = c  is  x = 0, y = c/b.
      if (b == 0 || c%b != 0) throw new ArithmeticException 
          ("No solution to the linear Diophantine equation "+a+"x + "+b+"y = "+c);
      else return new LongPair(0,c/b);
    } else if (b == 0) { // then a solution to  ax + 0y = c  is  x = c/a, y = 0.
      if (c%a != 0) throw new ArithmeticException 
          ("No solution to the linear Diophantine equation "+a+"x + "+b+"y = "+c);
      else return new LongPair(c/a,0);
    } else if (c%GCD(a,b) != 0) {
      throw new ArithmeticException 
      ("No solution to the linear Diophantine equation "+a+"x + "+b+"y = "+c);
    } // else there is a solution 
    // work with positive numbers
    long d = Math.abs(a);
    long e = Math.abs(b);  
    long x,y;
    if (d <= e) { // Divide d into e with quotient q and remainder r
      long q = e/d;   // so that e = qd + r.
      long r = e%d;   // Then a solution to the equation  dx + ey = c  is  x = z-q where
                 // the pair y, z is a solution to the equation  dz + ry = c
      LongPair solution = linearDiophantine(d,r,c);
      x = solution.getFirst() - q;
      y = solution.getSecond();
    } else {     // d>e
      long q = d/e;
      long r = d%e;   // d = qe + r.
      LongPair solution = linearDiophantine(r,e,c);
      x = solution.getFirst();
      y = solution.getSecond() - q;
    } // if/else  
    // take care of the signs
    if (a < 0) x = -x;
    if (b < 0) y = -y;
    return new LongPair(x,y);
  } // linearDiophantine  
  
  // Solve the linear Diophantine equation where the coefficients are this pair
  // of numbers
  public  LongPair linearDiophantine(long c) { return linearDiophantine(a,b,c); }
  

} // NumberTheory