Cod sursa(job #2356888)

Utilizator dimi999Dimitriu Andrei dimi999 Data 26 februarie 2019 22:48:59
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

int cmmdc,a,b;

int gcd(int a,int b)
{
    while(b!=0)
    {
        int aux=a;
        a=b;
        b=aux%b;
    }
    return a;
}

void euclid_extins(int a,int b,int &x,int &y)
{
    if(b==0)
        x=1,y=0;
    else
    {
        euclid_extins(b,a%b,x,y);
        int aux=y;
        y=x-(a/b)*y;
        x=aux;
    }
}

int main()
{
    int c,n;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>a>>b>>c;
        int x,y;
        cmmdc=gcd(a,b);
        if(c%cmmdc!=0)
            fout<<0<<" "<<0<<'\n';
        else
            {
                euclid_extins(a,b,x,y);
                fout<<x*(c/cmmdc)<<" "<<y*(c/cmmdc)<<'\n';
            }
    }

    return 0;
}