このディレクトリの索引
http://pc12.2ch.net/test/read.cgi/tech/1269438098/457
#   [2] 問題文(含コード&リンク): 
#   ・ユークリッドの互除法の拡張アルゴリズム 
#   入力 f1,f2 (f1>f2>0でよい)に対して、 
#   s*f1+t*f2=gcd(f1,f2)となる、s,tを求めよ。 
#   ただし、s,tは整数、gcd(f1,f2)はf1とf2の最大公約数である。また 配列を使わずに再現すること。 
#    

gcd_equal(_s * _f1 + _t * _f2 = _gcd) :-
      _f1 >= _f2,
      最大公約数をユークリッドの互除法で求める(_f1,_f2,_gcd),
      U is (_f1-_f2)) // _gcd,
      gcd_equal(1,U,_s,_f1,_t,_f2,_gcd).
gcd_equal(_s * _f1 + _t * _f2 = _gcd) :-
      _f2 > _f1,
      最大公約数をユークリッドの互除法で求める(_f2,_f1,_gcd),
      U is (_f2-_f1) // _gcd,
      gcd_equal(1,U,_t,_f2,_s,_f1,_gcd).

gcd_equal(N,0,_s,_f1,_t,_f1,_f1) :-
      gcd_equal(N,1, _s ,_f1,_t,_f1,_f1).
gcd_equal(N,U,_s,_f1,_t,_f2,_gcd) :-
      U2 is U * N,
      0 is (U2 * _f2 + _gcd) mod _f1,
      _t is U2 * (-1),
       _s  is (U2 * _f2 + _gcd) // _f1.
gcd_equal(N,U,_s,_f1,_t,_f2,_gcd) :-
      U2 is U * N,
      0 is (U2 * _f2 - _gcd) mod _f1,
       _s  is (U2 * _f2 - _gcd) // _f1 * (-1),
      _t is U2.
gcd_equal(N,U,_s,_f1,_t,_f2,_gcd) :-
      U2 is U * N,
      0 is (U2 * _f1 + _gcd) mod _f2,
       _s  is U2 * (-1),
      _t is (U2 * _f1 + _gcd) // _f2.
gcd_equal(N,U,_s,_f1,_t,_f2,_gcd) :-
      U2 is U * N,
      0 is (U2 * _f1 - _gcd) mod _f2,
      _t is (U2 * _f1 - _gcd) // _f2 * (-1),
       _s  is U2.
gcd_equal(N,U,_s,_f1,_t,_f2,_gcd) :-
      N2 is N + 1,
      gcd_equal(N2,U,_s,_f1,_t,_f2,_gcd).

最大公約数をユークリッドの互除法で求める(M,N,N) :-
      0 is M mod N,!.
最大公約数をユークリッドの互除法で求める(M,N,X) :-
      Mod is M mod N,
      最大公約数をユークリッドの互除法で求める(N,Mod,X).

最大公約数(M,N,X) :-
      最大公約数をユークリッドの互除法で求める(M,N,X),!.