Cod sursa(job #3369496)

Utilizator DavidboangiuBoangiu David Andrei Davidboangiu Data 20 octombrie 2026 17:42:18
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
pair <int,int> euclid(int a, int b)
{
    if(b==0)
    {
        return make_pair(1,0);
    }
    else
    {
        pair <int,int> p0=euclid(b,a%b);
        pair <int,int> p;
        p.first=p0.second;
        p.second=p0.first-(a/b)*p.first;
        return p;
    }
}
int t,a,b,c;
int main()
{
    f>>t;
    for(; t; t--)
    {
        f>>a>>b>>c;
        if(c%__gcd(a,b)) g<<"0 0" << '\n';
        else
        {
            pair<int,int> p=euclid(a,b);
            p.first*=c/__gcd(a,b);
            p.second*=c/__gcd(a,b);
            g<<p.first<<" "<<p.second<<'\n';
        }
    }
}