Cod sursa(job #1745450)

Utilizator catalin9898Bajenaru Catalin catalin9898 Data 21 august 2016 21:51:07
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <cstdio>
using namespace std;

void eu(int a,int b,int &div,int &x,int &y,int &x1,int &y1)
{
    if(b==0)
        {
            x1=1;
            div=a;
            y1=0;


        }
    else
    {
        eu(b,a%b,div,x,y,x1,y1);
        x=y1;
        y=x1-(a/b)*(y1);
        x1=x;
        y1=y;
    }

}

int main()
{
 freopen("euclid3.in","r",stdin);
 freopen("euclid3.out","w",stdout);
    int a,b,t,c,d,div,x,y,x1,y1;
    scanf("%d",&t);

    for(c=0;c<t;c++)
    {
        scanf("%d%d%d",&a,&b,&d);
        eu(a,b,div,x,y,x1,y1);
        if(d%div!=0)printf("0 0\n");
        else
        {
            x1=d/div;
            x=x*x1;
            y=y*x1;
            printf("%d %d\n",x,y);
        }

    }




    return 0;
}