アルゴリズム論特論（塩田）　2016年度教材

アルゴリズム論特論（塩田）　2016年度教材　第3回

授業内容
- ユークリッドのアルゴリズム
  - gcd のみ求めるアルゴリズム
  - gcd のみ求めるアルゴリズム再帰 version
  - gcd(a, b) = a x + b y を満たす x, y も求めるアルゴリズム再帰 version
  - gcd(a, b) = a x + b y を満たす x, y も求めるアルゴリズム
- ユークリッドのアルゴリズムの計算量

ツボ
- n 以下2つのの自然数を引数とするユークリッドのアルゴリズムの計算量は O(log²n)

問題
- 下記の場合については gcd(a,b) = 1 であることがわかっている。ユークリッドのアルゴリズムを用いてそれぞれ a x + b y = 1 を満たす整数の組 (x, y) をひとつ求めよ。