アルゴリズム/拡張ユークリッド互除法

Thu, 05 Aug 2010 18:57:45 JST (29d)

拡張ユークリッド互除法

仕様

プログラム概要

拡張ユークリッド互除法の実装

入力

0でない自然数x,y

出力

ax+by=cとなるa,bの値 ただし、cはxとyの最大公約数

プログラム

じょり:

半分寝ながらつくりました。正直あってんのか謎w んでも解ける、うん。間違いおしえて♪ ( aとbがmとnになってまふmx+my=gcd(x,y))

ろぎ:

再帰的に。。。 http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html ここ参考にした。ていうかここの解説をそのまま実装。

コメント