Cod sursa(job #2128948)

Utilizator alex90001alex ilioi alex90001 Data 12 februarie 2018 12:25:07
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("euclid3.in");
ofstream g("euclid3.out");

int cmmdc(int a,int b)
{
    int rest;
    if(a < b)
    {
        rest = a;
        a = b;
        b = rest;
    }
    do
    {
        rest = a % b;
        a = b;
        b = rest;
    }while(rest != 0);
    return a;
}

void euclid(int a,int b,int *d,int *x,int *y)
{
    if(b == 0)
    {
        *x = 1;
        *y = 0;
        *d = a;
    }
    else
    {
        int x0,y0;
        euclid(b,a%b,d,&x0,&y0);
        *x = y0;
        *y = (a/b)*y0 - x0;
    }
}

int main()
{
    int a,b,c,x,y,d,n,i;
    f>>n;
    for(i = 1;i <= n;i++)
    {
        f>>a>>b>>c;
        d = cmmdc(a,b);
        if(c%d != 0)
        {
            x = 0;
            y = 0;
        }
        else
        {
        euclid(a,b,&d,&x,&y);
        x = x * c/d;
        y = y * c/d;
        }
        g<<x<<" "<<y<<"\n";
    }

    return 0;
}