Cod sursa(job #1750127)

Utilizator bogdanluncasubogdan bogdanluncasu Data 29 august 2016 17:06:28
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <stdio.h>
using namespace std;
int euclid(int a,int b){
	if(b==0)return a;
	euclid(b,a%b);
}

int v0[2],v1[2],vt[2];
void solution(int a,int b,int c){
	int cmmdc=euclid(a,b),q,r;
	if(c%cmmdc!=0)cout<<0<<" "<<0<<endl;
	else{
		if(cmmdc!=1){
			a=a/cmmdc,b=b/cmmdc,c=c/cmmdc;
		}
		if(a<b){
			int t=a;a=b,b=t;
			v0[0]=0,v0[1]=1,v1[0]=1,v1[1]=0;
		}else{
			v0[0]=1,v0[1]=0,v1[0]=0,v1[1]=1;
		}
		while(b!=0){
			q=a/b;
			r=a%b;
			a=b,b=r;
			vt[0]=v0[0],vt[1]=v0[1];
			v0[0]=v1[0],v0[1]=v1[1];
			v1[0]=vt[0]-q*v1[0];
			v1[1]=vt[1]-q*v1[1];
		}
		
		cout<<(c/cmmdc)*v0[0]<<" "<<(c/cmmdc)*v0[1]<<endl;
	}
}

int main() {
	freopen("euclid3.in", "r", stdin);
	freopen("euclid3.out", "w", stdout);
	int x,y,z,t;
	scanf("%d", &t);
	for(int i=0;i<t;i++){
		scanf("%d %d %d", &x,&y,&z);
		solution(x,y,z);
	}
}