Cod sursa(job #361212)

Utilizator cristiprgPrigoana Cristian cristiprg Data 4 noiembrie 2009 10:20:35
Problema Algoritmul lui Euclid extins Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<cstdio>

const int CATVA = 1<<30;

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

int main()
{
	FILE *f = fopen("euclid3.in", "r");
	FILE *g = fopen("euclid3.out", "w");
	int a, b, c, t;
	fscanf(f, "%d", &t);
	
	
	for (int i = 1; i <= t; ++i)
	{
		fscanf(f, "%d%d%d", &a, &b, &c);
		if (a == 0 && b == 0)
		{
			fprintf(g, "0 0\n");
			break;
		}
		
		if (a == 0)
			if (c % b == 0)
			{
				fprintf(g, "0 %d\n", c/b);
				break;
			}
			else
			{
				fprintf (g, "0 0\n");
				break;
			}
		
		if (b == 0)	
			if (c % a == 0)
			{
				fprintf(g, "%d 0\n", c/a);
				break;
			}
			else
			{
				fprintf (g, "0 0\n");
				break;
			}
	
				
		
		int d = cmmdc(a, b);
		if (c % d != 0)
		{
			fprintf(g,  "0 0 \n");
			break;
		}
		
		
			
		for (int x = 1; x <= CATVA; ++x)
		
			if ((c - a * x) % b == 0)
			{
				fprintf (g,  "%d %d\n", x, (c - a * x) / b);
				break;
			}
	}
	fclose(f);
	fclose(g);
	return 0;
	
}