Cod sursa(job #3220781)

Utilizator Gabriel_DaescuDaescu Gabriel Florin Gabriel_Daescu Data 4 aprilie 2024 20:10:08
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
using namespace std;
ifstream  fin("euclid3.in");
ofstream fout("euclid3.out");
int T,a,b,i,x,y;
long long c;

int euclidsimplu(int x,int y)
{
    int a,b,r;
    a=x;
    b=y;
    r=0;

    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }

    return a;

}

void euclidextins(int a,int b,int &x,int &y)
{
    int k=0,a1[102],b1[102],x1[102],y1[102];
    a1[0]=a;
    b1[0]=b;

    while(b1[k]!=0)
    {
        int r=a1[k]%b1[k];
        k++;
        a1[k]=b1[k-1];
        b1[k]=r;
    }

    x1[k]=1;
    y1[k]=0;

    for(int i=k-1; i>=0; i--)
    {
        x1[i]=y1[i+1];
        y1[i]=x1[i+1]-a1[i]/b1[i]*y1[i+1];
    }

    x=x1[0];
    y=y1[0];
}

int main()
{
    fin>>T;

    for(i=1; i<=T; i++)
    {
        fin>>a>>b>>c;
        int d=euclidsimplu(a,b);
        if(c%d!=0)
        {
            fout<< 0 << " " << 0 << "\n";
        }
        else
        {
            euclidextins(a,b,x,y);
            x=x*(c/d);
            y=y*(c/d);
            fout<< x << " " << y << "\n";
        }

    }

    return 0;
}