Extended Euclid(User defined types)¶

type
  node
  {
    int d;
    int s;
    int t;
  }
endtype

decl
  node y,z,gcd(int a,int b);
enddecl

node gcd(int a,int b)
{
  decl
    int q,r,temp;
  enddecl

  begin
    if(b==0) then
      y.d = a;
      y.s = 1;
      y.t = 0;
    else
      q = a/b;
      r = a%b;
      z = gcd(b,r);
      temp = z.s;
      y.s = z.t;
      y.t = temp - (q*z.t);
    endif;

  return y;
  end
}

int main()
{
  decl
    node res;
    int a,b,c;
  enddecl

  begin
    c = initialize();
    y = alloc();
    read(a);
    read(b);
    res = gcd(a,b);
    write(res.d);
    write(res.s);
    write(res.t);

  return 0;
  end
}