扩展欧几里得算法（Lisp）

 

(defun ex-gcd (a b)
    (if (= b 0) (values 1 0 a)
        (let ((x 0) (y 0) (r 0) (tmp 0))
            (multiple-value-bind (x y r) (ex-gcd b (mod a b))
                (setf
                    tmp y
                    y   (- x (* (floor (/ a b)) y))
                    x   tmp)
                (values x y r)))))

(let ((x 0) (y 0) (r 0))
    (multiple-value-bind (x y r) (ex-gcd 72 98)
        (format t "X:~D Y:~D R:~D~%" x y r)
        (format t "~D~%" (+ (* 15 72) (* -11 98)))))