Cod sursa(job #1224128)

Utilizator RaileanuCristian Raileanu Raileanu Data 29 august 2014 20:43:27
Problema Algoritmul lui Euclid extins Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 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 ; }
        else
        {   for (y=0; y<=2000000 && labs(y*b)%labs(a)!=1; y++ );
                x= y*b/a ; }
    if (abs(a)>abs(b) )
    {   if (a*x<0 ) x*=-1;
        if (b*y>0) y*=-1; }
    else
    { if (a*x>0 ) x*=-1;
      if (b*y<0) y*=-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;
}