Cod sursa(job #1816494)

Utilizator cosminmaneaCosmin Manea cosminmanea Data 26 noiembrie 2016 15:53:50
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>

using namespace std;

int cmmdc(int a,int b)
{
    if(b==0) return a;
    return cmmdc(b,a%b);
}

int n,a,b,c,cat[100000];

int main()
{
    FILE *f=fopen("euclid3.in","r");
    FILE *g=fopen("euclid3.out","w");
    fscanf(f,"%d",&n);
    int i;
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        int d=cmmdc(a,b);
        if(c%d==0)
        {
            int nr=0,p,z,x,y;
            p=a;
            z=b;
            while(b)
            {
                cat[++nr]=a/b;
                a=b;
                b=p%z;
                p=a;
                z=b;
            }
            p=x=d/a;
            z=y=0;
            for(i=nr;i>=1;i--)
            {
                x=y;
                y=p-cat[i]*z;
                p=x;
                z=y;
            }
            x=x*(c/d);
            y=y*(c/d);
            fprintf(g,"%d %d\n",x,y);
        }
        else fprintf(g,"0 0\n");
    }
    return 0;
}