Cod sursa(job #1518954)

Utilizator andreii1Ilie Andrei andreii1 Data 6 noiembrie 2015 16:33:10
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cstdio>

using namespace std;

long long solA,solB,x,y,cmmdc,z;

void euclid(long long a,long long b)
{
    long long r,d;
    long long c1=1,d1=0;
    long long c2=0,d2=1;
    long long c3,d3;
    while(b!=0)// (a,b) -> (b, b%a);
    {
        r=a%b;
        d=a/b;
        c3=c1-d*c2;
        d3=d1-d*d2;
        c1=c2;d1=d2;
        c2=c3;d2=d3;
        a=b;
        b=r;
    }
    cmmdc=a;
    solA=c1;
    solB=d1;
}

int main()
{
    long long ii,T;
    FILE *f=fopen("euclid3.in","r");
    FILE *g=fopen("euclid3.out","w");
    fscanf(f,"%lld",&T);
    for(long long ii=1;ii<=T;ii++)
    {
    fscanf(f,"%lld %lld %lld",&x,&y,&z);
    euclid(x,y);
    if(z%cmmdc==0)fprintf(g,"%lld %lld\n",solA*(z/cmmdc),solB*(z/cmmdc));
    else fprintf(g,"0 0\n");
    }
    fclose(f);
    fclose(g);
    return 0;
}