Cod sursa(job #2038926)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 14 octombrie 2017 10:04:09
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <cstdio>
using namespace std;
pair<long long,long long> euclidExtins(long long a,long long b)
{
    if(!b)
        return make_pair(1,0);
    pair<long long,long long> p=euclidExtins(b,a%b);
    return make_pair(p.second,p.first-p.second*(a/b));
}
int main()
{
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
    long long n,a,b,c;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld",&a,&b,&c);
        if(a<b)
            swap(a,b);
        pair<long long,long long> rez=euclidExtins(a,b);
        long long cmmdc=a*rez.first+b*rez.second;
        if(c%cmmdc==0)
            printf("%lld %lld\n",rez.first*c/cmmdc,rez.second*c/cmmdc);
        else
            printf("0 0\n");
    }
    return 0;
}