Linear Congruences by kaki

#!ruby -rmathn
r=[]
$_[1]?(~/(\d+)\D*(\d+)/;r<<[$1.to_i,$2.to_i]):puts((_=r.inject([0,1]){|(a,b),(c,d)|c<d||break;c-=a;c%=d;c/=g=b.gcd(c.gcd d);d/=g;(c=(1..d*v=b/g).find{|i|i*v%d==c})?[a+b*c%(t=b*d),t]:break})?_*" + "+"k":"no solutions")||r=[]while gets

Note that non-ascii characters in the above source code will be escaped (such as \x9f).

download

return to the top page