Cod sursa(job #1508712)

Utilizator timicsIoana Tamas timics Data 22 octombrie 2015 21:30:30
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<iostream>
#include<stdio.h>
using namespace std;
int  T,a,b,c,x,y;

int gcd(int a, int b, int &x, int &y) {
    if(b==0) {
        x=1;
        y=0;
        return a;
    }
    else {
        int x0,y0;
        int d = gcd(b,a%b,x0,y0);
        x = y0;
        y = x0 - a/b *y0;
        return d;
    }
}
 
pair<int,int> euclid(int a, int b, int c) {
    int x, y;
    int d = gcd(a,b,x,y);
    if(c%d) {
        return make_pair(0,0);    
    }
    int sol1 = (c/d)*x;
    int sol2 = -(c/d)*y;

    /*while(sol1 < 0 || sol2 < 0) {
        sol1 += b/d;
        sol2 += a/d;
    }
    while(sol1 >= b/d || sol2 >= a/d) {
        sol1 -= b/d;
        sol2 -= a/d;
    }*/
    return make_pair(sol1,sol2);
}

int main() {
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
    scanf("%d",&T);
    for(int i=1;i<=T;++i) {
        scanf("%d%d%d",&a,&b,&c);
        pair<int,int> p = euclid(a,b,c);
        printf("%d %d\n",p.first,p.second); 
    }
    return 0;
}