Cod sursa(job #3138467)

Utilizator proflaurianPanaete Adrian proflaurian Data 19 iunie 2023 18:55:35
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
int t,a,b,c;
int cmmdc(int a,int b,int &u,int &v)/// returneaza cmmdc(a,b) si prin intermediul parametrilor u si v valorile pt care au+bv=d
{
    if(b==0)
    {
        u=1;v=0;
        return a;
    }
    /// cmmdc(a,b) = cmmdc(b,a%b)
    int U,V,D;
    D=cmmdc(b,a%b,U,V);
    u=V;
    v=U-(a/b)*V;
    return D;
}
int main()
{
    f>>t;
    for(;t;t--) /// "de t ori"
    {
        f>>a>>b>>c;
        int d,u,v;
        d=cmmdc(a,b,u,v);
        int x,y;
        if(c%d!=0)
        {
            x=0;
            y=0;
        }
        else
        {
            x=(c/d)*u;
            y=(c/d)*v;
        }
        g<<x<<' '<<y<<'\n';
    }

    return 0;
}