https://www.spoj.com/problems/DCEPC11B/

solution.lisp

(defun diophantine-equation (a b)
  (declare (fixnum a) (fixnum b)
           (optimize (speed 3)))
  (let ((left-side-a 1) (left-side-b 0)
        (right-side-a 0) (right-side-b 1))
    (declare (fixnum left-side-a) (fixnum left-side-b)
             (fixnum right-side-a) (fixnum right-side-b))
    (loop :until (or (= 0 a) (= 0 b))
          :if (> a b)
            :do (multiple-value-bind (q r) (floor a b)
                  (setf a r)
                  (decf left-side-a (* q right-side-a))
                  (decf left-side-b (* q right-side-b)))
          :else
            :do (multiple-value-bind (q r) (floor b a)
                  (setf b r)
                  (decf right-side-a (* q left-side-a))
                  (decf right-side-b (* q left-side-b)))
          :finally (if (= 0 a)
                       (return (values b right-side-a right-side-b))
                       (return (values a left-side-a left-side-b))))))







(defun quickfactorial (N P)
  (declare (fixnum N) (fixnum P)
           (optimize (speed 3)))
  (if (< N P)
      (let ((inv (loop :for j :from (1+ N) :below P
                       :for res :of-type fixnum := j :then (mod (* res j) P)
                       :finally (return (mod res P)))))
        (mod (- P (the fixnum (nth-value 1 (diophantine-equation inv P)))) P))
      0))



(defun main ()
  (loop :with tests := (read)
        :repeat tests
        :collect (quickfactorial (read) (read)) :into results
        :finally (map nil (lambda (x) (format t "~s~%" x)) results)))