Cod sursa(job #1558173)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 28 decembrie 2015 19:52:01
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int r,d;
struct sp
{
    int x,y;
};
sp euclid(int a,int b)
{
    sp ans,tm;
    int c;
    if(b!=0)
    {
    c=a/b;
    tm=euclid(b,a%b);
    ans.x=tm.y;
    ans.y=tm.x-tm.y*c;
    return ans;
    }
    else
    {
        ans.x=1;
        ans.y=0;
        d=a;
        return ans;
    }
}
int main()
{
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
    int t,q,a,b,r;
    sp ans;
    scanf("%d",&t);
    for(q=1;q<=t;q++)
    {
    scanf("%d%d%d",&a,&b,&r);
    if(b<a)
    ans=euclid(a,b);
    else
    ans=euclid(b,a);
    if(r%d!=0)
    printf("0 0\n");
    else
    if(b<a)
    printf("%d %d\n",ans.x*(r/d),ans.y*(r/d));
    else
    printf("%d %d\n",ans.y*(r/d),ans.x*(r/d));
    }
    return 0;
}