Cod sursa(job #1224127)

Utilizator RaileanuCristian Raileanu Raileanu Data 29 august 2014 20:32:04
Problema Algoritmul lui Euclid extins Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include<stdlib.h>

using namespace std;
int a,b,c, x,y,t,i;

int cmmdc(int a1, int b1)
{
    int c1;
    while (b1>0)
    {
        c1=b1;
        b1=a1 % b1;
        a1=c1;
    }
    return a1;
}

void rez()
{
    int d,s,i;
    d=cmmdc(abs(a) ,abs(b) );
    if ((abs(c)%d) !=0 ) {x=0; y=0; return; }

    if (c>0) s=1; else s=-1;
    a/=d*s;
    b/=d*s;
    if (abs(b)==1) {x=1; y=a-1; } else
    if (abs(a)==1 ) {x=b-1; y=1; } else
    if (abs(a) > abs(b) )
        {   for (x=0; x<=2000000 && labs(x*a)%labs(b) !=1; x++ );
            y= x*a/b ;
            if (x*a<0) x*=-1;
            if (y*b>0) y*=-1; }
        else
        {   for (y=0; y<=2000000 && labs(y*b)%labs(a)!=1; y++ );
                x= y*b/a ;
                if (y*b<0) y*=-1;
                if (x*a>0) x*=-1; }
    x*=abs(c)/d;
    y*=abs(c)/d;
}

int main()
{
    ifstream f1("euclid3.in");
    ofstream f2("euclid3.out");

    f1>>t;
    for (i=1; i<=t; i++ )
    {
        f1>>a>>b>>c;
        rez();
        f2<<x<<" "<<y<<"\n";
    }

    f1.close();
    f2.close();
    return 0;
}