Cod sursa(job #2026734)

Utilizator sandruSandru Petru-Ionut sandru Data 24 septembrie 2017 22:35:12
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <stdio.h>

struct triplet{
	int d;
	int x;
	int y;
} trip;

void euclid(int a, int b)
{
    if (b == 0) {
    	trip.d=a;
    	trip.x=1;
    	trip.y=0;

    }
    else {
    	euclid(b,a%b);
    	int x = trip.y;
    	trip.y=trip.x-(a/b)*trip.y;
    	trip.x =x;
    }
}

int main() {
	int t;
	int a,b,c;
	freopen("euclid3.in","r", stdin);
	freopen("euclid3.out", "w", stdout);
	scanf("%d",&t);
	for(int i=0;i<t;i++)
	{
		scanf("%d %d %d", &a,&b,&c);
		euclid(a,b);
		if(c%trip.d==0)
			printf("%d %d\n",trip.x*(c/trip.d),trip.y*(c/trip.d));
		else
			printf("0 0\n");
	}
return 0;
}