Cod sursa(job #1224223)

Utilizator RaileanuCristian Raileanu Raileanu Data 30 august 2014 10:13:48
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include<stdlib.h>

#define MX 2000000000
using namespace std;
int a,b,c, t,i;
long long x,y;

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

int solutie(int j)
{
    if (j>= -MX && j<= MX ) return 1;
    else return 0;
}

void rez(int a, int b)
{
    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
        {   for (x=0; x<=5000000 && (labs(x*a)%labs(b) !=1 || labs(x*a)<=b) ; x++ );
            y= x*a/b ; }

    if (a*x<0 ) x*=-1;
        if (b*y>0) y*=-1;

    x*=abs(c)/d;
    y*=abs(c)/d;
    if (!solutie(x) || !solutie(y) ) {x=0; y=0; }
}

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

    f1>>t;
    for (i=1; i<=t; i++ )
    {
        f1>>a>>b>>c;
        rez(a,b);
        if (x==0 && y==0)
            { rez(b,a);
              int aux=x;
              x=y;
              y=aux; }

        f2<<x<<" "<<y<<"\n";
    }

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