Cod sursa(job #758410)

Utilizator iris88Nagy Aliz iris88 Data 15 iunie 2012 16:42:30
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#include <iostream>
#include <fstream>
#include <list>
#include <limits.h>
#include <stdio.h>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stdio.h>
#include <algorithm>
#include <deque>
#include <string.h>

using namespace std;

void swap(long long &a, long long&b)
{
	if (a==b) return;
	a = a^b;
	b = a^b;
	a = b^a;
}
//a>b
void euclid_ext(long long a, long long b,long long &d,long long &x, long long &y)
{	
	if (b==0){
		d =a;
		x = 1;
		y =0;
	}
	else
	{
		long long k = a%b;
		long long c = a/b;
		long long x0=0,y0=0;
		a=b;
		b=k;
		euclid_ext(a,b,d,x0,y0);
		y = x0-c*y0;
		x = y0;
	}		
}
int main()
{
	FILE* f =  fopen("euclid3.in","r");
	FILE* g = fopen("euclid3.out","w+");
	int T;
	fscanf(f,"%d",&T);
	for (int i=0;i<T;i++)
	{
		long long gr = 0;
		long long a,b,c,d,x,y;		
		fscanf(f,"%lld %lld %lld", &a,&b, &c);
		if (abs(a)<abs(b)) {swap(a,b);gr=1;}
		euclid_ext(a,b,d,x,y);
		if (c%d ==0)
		{
			x = x*c/d;
			y = y*c/d;
			if (gr) swap(x,y);
			fprintf(g,"%lld %lld\n",x,y);
		}
		else
			fprintf(g,"0 0\n");
		
	}
	fclose(f);
	fclose(g);
}