拡張ユークリッドの互除法を自己流で実装してみた。

蟻本のやつがあまりに難しくて理解できなかったのと、何か使いにくそうだったので自分で実装してみた。 こっちのほうが素直で分かりやすいと思う。

#include<cstdio>
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> P;

//solution of xa+yb=gcd(a,b)
P extgcd(int a, int b){
  if(b==0)
    return P(1, 0);

  P p = extgcd(b, a%b);
  int x = p.first;
  int y = p.second;

  return P(y, x - y*(a/b));
}

int main(){
  int a=15, b=12;
  P p = extgcd(a,b);
  cout << p.first << " " << p.second << endl;

  return 0;
}