Cod sursa(job #1053041)

Utilizator deea101Andreea deea101 Data 12 decembrie 2013 01:57:11
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <iostream>

using namespace std;
ifstream f("euclid3.in");
ofstream g("euclid3.out");

int mod(int a)
{
	if(a>=0) return a%3;
	else return (3+a)%3;
}
int main()
{
	int T,a,b,c,q;
	int x[3]={1,0},y[3]={0,1},r[3],i=0;
	f>>T;
	
	while(T--)
	{
		i=1;
		f>>a>>b>>c; 
		if(!a) {
			if(c%b==0) g<<0<<' '<<c/b<<'\n';
			else g<<0<<' '<<0<<'\n';
			continue;
		}
		if(!b)
		{
			if(c%a==0) g<<c/a<<' '<<0<<'\n';
			else g<<0<<' '<<0<<'\n';
			continue;
		}	

		r[0]=a; r[1]=b; 
		x[0]=1; y[0]=0; 
		x[1]=0; y[1]=1;
		while(r[mod(i-1)]%r[i] != 0)
		{
			i=(i+1)%3;
			r[i]=r[mod(i-2)]%r[mod(i-1)];
			
			q=r[mod(i-2)]/r[mod(i-1)];
			x[i]=x[mod(i-2)]-x[mod(i-1)]*q;
			y[i]=y[mod(i-2)]-y[mod(i-1)]*q;
		}
		
		if(c%r[i]!=0) g<<0<<' '<<0<<'\n';
		else g<<x[i]*(c/r[i])<<' '<<y[i]*(c/r[i])<<'\n';
	}
}