« やってしまった・・・ | トップページ | Advanced/W-ZERO3[es]のアカデミックパック »

2007/10/29

拡張ユークリッドを用いたプログラム

以前からユークリッドのことで騒いでいましたが、プログラムを載せてみたいと思います。

問題は次のようになっています。

「正整数a, bを入力し、拡張ユークリッド互除法を用いて、gcd(a, b) = 1ならば、ax ≡1 mod bの解xを返し、gcd(a, b) ≠ 1ならば、0を返すプログラムをつくれ」

私の作ったプログラムを以下のリンク先にアップしてあります。(実は、だいぶ前にできていましたが、大学の課題なので自分が提出するまではアレかなぁと思いまして)

#include 
#include 

//拡張ユークリッドのアルゴリズム
int add_gcd(int a, int b, int *ans_x, int *ans_y, int *ans_gcd)
{
  int r_pre = a, r = b, r_next;
  int x_pre = 1, x = 0, x_next;
  int y_pre = 0, y = 1, y_next; 
  int q, k = 1;
  int ans;

  while((r_next = r_pre % r) != 0) {
    q      = r_pre / r;
    k++;
    x_next = q * x + x_pre;
    y_next = q * y + y_pre;
    //---変数を更新---
    r_pre = r;
    r     = r_next;
    x_pre = x;
    x     = x_next;
    y_pre = y;
    y     = y_next;
  }
  //不定方程式の解を求める
  *ans_x = pow(-1, k)   * x;
  *ans_y = pow(-1, k+1) * y;
  //最大公約数を計算
  *ans_gcd = (*ans_x * a) + (*ans_y * b);

  //---逆元を求める(逆元は正)---
  if(*ans_gcd == 1) {
    ans = (*ans_x + b) % b;
  } else {
    ans = 0;
  }
  //逆元もしくは0を返す
  return (ans);
}

int main(void)
{
  int n1, n2;
  int ans1, ans2, gcd;
  int output;

  puts("==============================");
  printf("整数1:");   scanf("%d", &n1);
  printf("整数2:");   scanf("%d", &n2);
  //---拡張ユークリッドアルゴリズムを計算---
  output = add_gcd(n1, n2, &ans1, &ans2, &gcd);
  puts("------------------------------");
  printf("%dx + %dy = %d\n", n1, n2, gcd);
  printf("(x, y) = (%d, %d)\n", ans1, ans2);
  //---ax懼1(mod n)を満たすx---
  puts("------------------------------");
  if(gcd == 1) {
    printf("%d * %d 懼 1 (mod %d)\n", n1, output, n2);
    printf("求める逆元:%d\n", output);
  } else {
    printf("gcd(%d,%d) 懼 1 より%d\n", n1, n2, output);
  }
  puts("==============================");

  return 0;
}

このプログラムでは変数を入れ替えて処理を進めるようにしています。(下手に配列でやるといろいろ制約ができてしまうので)

|

« やってしまった・・・ | トップページ | Advanced/W-ZERO3[es]のアカデミックパック »

Algorithm」カテゴリの記事

C」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/222903/16915606

この記事へのトラックバック一覧です: 拡張ユークリッドを用いたプログラム:

« やってしまった・・・ | トップページ | Advanced/W-ZERO3[es]のアカデミックパック »