Cod sursa(job #1762472)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 23 septembrie 2016 16:17:35
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <stdio.h>
#include <stdlib.h>

#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline long long nextnum(){
    long long a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}

void cmmdc(long long a, long long b, long long &x, long long &y){
    if(b==0){
        x=1;
        y=0;
    }
    else{
        long long x1, y1;
        cmmdc(b, a%b, x1, y1);
        x=y1;
        long long c=a/b;
        y=x1-c*y1;
    }
}

int main(){
    fi=fopen("euclid3.in","r");
    fo=fopen("euclid3.out","w");
    long long n=nextnum();
    for(int i=0;i<n;i++){
        long long a=nextnum(), b=nextnum(), c=nextnum();
        long long a1, b1, r;
        a1=a;
        b1=b;
        while(b1!=0){
            r=a1%b1;
            a1=b1;
            b1=r;
        }
        if(c%a1!=0)
            fprintf(fo,"0 0\n");
        else{
            long long x, y;
            cmmdc(a, b, x, y);
            fprintf(fo,"%lld %lld\n", x*c/a1, y*c/a1);
        }
    }
    fclose(fi);
    fclose(fo);
    return 0;
}