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 !