Cod sursa(job #1205484)

Utilizator andreas.chelsauAndreas Chelsau andreas.chelsau Data 6 iulie 2014 21:52:10
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;

void extendedEuclid(ll a, ll b,ll c){
	ll x1 = 1,y1 = 0,x2 = 0,y2 = 1;
	while(b){
		ll r = a % b;
		ll x = x2,y = y2;
		x2 = x1 - (a / b) * x2;
		y2 = y1 - (a / b) * y2;
		x1 = x,y1 = y;
		a = b; b = r;
	//	cout<<x2<<" "<<y2<<'\n';
		
	}
	if(c % a == 0)
		printf("%lld %lld\n",(c / a) * x1,(c / a) * y1);
	else
		printf("0 0\n");

}
int main(){
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
	ll a,b,c;
	int t;
	scanf("%d",&t);
	for(int i = 0; i < t; i++){
		scanf("%lld%lld%lld",&a,&b,&c);
		extendedEuclid(a,b,c);
	}
	return 0;
}