Cod sursa(job #1690262)

Utilizator andreilucaLuca Andrei andreiluca Data 14 aprilie 2016 22:02:20
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
FILE *in, *out;
struct ve
{
	int alfa;
	int beta;
};
void solve();// deci uite am functia asta care e comentata. daca o decomentez imi da eroare de linking
ve euclid_extins(int a,int b ,int c );
int cmmdc(int a, int b);

int main()
{
	in = fopen("euclid3.in", "r");
	out = fopen("euclid3.out", "w");
	//printf("%d", cmmdc(15, 25));
	solve();
	return 0;
}
void solve()
{
	int n;
	ve v;
	fscanf(in,"%d", &n);
	int a, b, c;
	for (int i = 0; i < n; i++)
	{
		fscanf(in, "%d%d%d", &a, &b, &c);
		v = euclid_extins(a, b, c);
		fprintf(out,"%d %d\n",v.alfa*(c/cmmdc(a,b)),v.beta*(c/cmmdc(a,b)));
	}
};
ve euclid_extins(int a, int b, int c)
{
	//int d = cmmdc(a, b);
	int rest;
	ve v1, v2, v3;
	if (b > a)
		std::swap(a, b);
	if (c%cmmdc(a,b)!=0)
	{
		ve v;
		v.alfa = 0;
		v.beta = 0;
	}
	v1.alfa = 1;
	v1.beta = 0;
	v2.alfa = 0;
	v2.beta = 1;
	if (a%b==0)
		return v2;
	rest = a%b;
	while (rest)
	{
		rest = a %b;
		v3.alfa = v1.alfa - (a / b)*v2.alfa;
		v3.beta = v1.beta - (a / b)*v2.beta;
		v1 = v2;
		v2 = v3;
		a = b;
		b = rest;
	}
	return v1;
};
int cmmdc(int a, int b)
{
	if (b > a)
		std::swap(a, b);
	if (a%b == 0)
		return b;
	int rest = a%b;
	while (rest)
	{
		rest = a%b;
		a = b;
		b = rest;
	}
	return a;
};