Cod sursa(job #1261264)

Utilizator gabimoiseMoise Gabriel gabimoise Data 12 noiembrie 2014 08:46:31
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <cstdio>

using namespace std;

int i,t,a,b,c,aux1,aux2,r,x,y,d;
void euclid(int a,int b,int &d,int &x,int &y)
{
   if (b==0) {
                d=a;
                x=1;
                y=0;
             }
      else {
              int x0,y0;
              euclid(b,a%b,d,x0,y0);
              x = y0;
              y = x0-(a/b)*y0;
           }
}
int main()
{
  freopen("euclid3.in","r",stdin);
  freopen("euclid3.out","w",stdout);
  scanf("%ld",&t);
  for (i=1;i<=t;i++)
  {
      scanf("%ld%ld%ld",&a,&b,&c);
      aux1=a; aux2=b;
      do
        {
            r=aux1%aux2;
            aux1=aux2;
            aux2=r;
        }
      while (r!=0);
      d=aux1;
      x=0; y=0;
      euclid(a,b,d,x,y);
      if (d!=0) {x=x*(c/d); y=y*(c/d);}
      if (d!=0) if (c%d==0) printf("%d %d\n",x,y);
         else printf("%d %d\n",0,0);
  }
  return 0;
}