Cod sursa(job #1551204)

Utilizator tudor_bonifateTudor Bonifate tudor_bonifate Data 15 decembrie 2015 14:09:48
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
using namespace std;
int t,i,a,b,c,cmmdc,x,y;
int euclid(int a,int b)
{
    int r=a%b;
    while (r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}
int euclid_extins(int a, int b, int &x, int &y)
{
    int x0=1;
    int y1=1;
    int x1=0;
    int y0=0;
    int r=a%b;
    int c=a/b;
    while (r!=0)
    {
        x=x0-c*x1;
        y=y0-c*y1;
        x0=x1;
        x1=x;
        y0=y1;
        y1=y;
        a=b;
        b=r;
        r=a%b;
        c=a/b;
    }
}
int main()
{
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
    scanf("%d\n",&t);
    for (i=1; i<=t; i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        cmmdc=euclid(a,b);
        if (c%cmmdc!=0) printf("0 0\n");
        else
        {
            euclid_extins(a,b,x,y);
            printf("%d %d\n",x*(c/cmmdc),y*(c/cmmdc));
        }
    }
    return 0;
}