Saurez-vous résoudre des équations diophantiennes ? - Solution

On se retrouve aujourd'hui pour la solution du précédent #KataOfTheWeek proposé par Alex en début de semaine !

Voici une proposition de solution en Java:

public class EuclideUtils {

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


    public static Pair<Long, Long> manualEuclide(long a, long b, long c) {
        if (c == 0) {// (0, 0) is a solution
            return new ImmutablePair<>(0L,0L);
        } else if (a == 0) {
            if (b == 0 || c%b != 0) throw new ArithmeticException
                    ("No solution to the linear Diophantine equation " + a + "x + " + b + "y = " + c);
            else return new ImmutablePair<>(0L, c/b);//(0, c/b) is a solution 
        } else if (b == 0) {
            if (c%a != 0) throw new ArithmeticException
                    ("No solution to the linear Diophantine equation " + a + "x + " + b + "y = " + c);
            else return new ImmutablePair<>(c/a, 0L);//(c/a, 0) is a solution
        } else if (c%GCD(a,b) != 0) {//GCD(a, b) does  not divide c
            throw new ArithmeticException
                    ("No solution to the linear Diophantine equation " + a + "x + " + b + "y = " + c);
        }
        //a = q*b + r
        long q = a/b;
        long r = a%b;
        if (r == 0) return new ImmutablePair<>(0L, c/b);
        else {
            Pair sol = manualEuclide(b, r, c);
            long u = (long) sol.getLeft();
            long v = (long) sol.getRight();
            return new ImmutablePair<>(v, u - q * v);
        }
    }
}

A bientôt pour un nouveau #KataOfTheWeek !