Cod sursa(job #3004046)

Utilizator stefantagaTaga Stefan stefantaga Data 16 martie 2023 09:15:07
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>

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