Cod sursa(job #2272599)

Utilizator cezar.plescaCezar Plesca cezar.plesca Data 30 octombrie 2018 13:25:28
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include<stdio.h>
#include<math.h>

long long a,b,c;

void euclid(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 x0, y0;
        euclid(b, a % b, d, &x0, &y0);
        *x = y0;
        *y = x0 - (a / b) * y0;
    }
}


int main(){
	int T;
	FILE* f= fopen("euclid3.in","rt");
	FILE* g= fopen("euclid3.out","wt");
	fscanf(f,"%d",&T);

	long long d, x, y;
	for(int i=0;i<T;i++){
		fscanf(f,"%lld %lld %lld",&a,&b,&c);		
		
		if(a==0){
			if(b==0){
				fprintf(g,"0 0\n");
				continue;
			}
			else{
				if(c%b==0){
					fprintf(g,"%lld %lld\n",0,c/b);
					continue;
				}
				else{
					fprintf(g,"0 0\n");
					continue;
				}
			}
		}

		if(b==0){
			if(a==0){
				fprintf(g,"0 0\n");
				continue;
			}
			else{
				if(c%a==0){
					fprintf(g,"%lld %lld\n",c/a,0);
					continue;
				}
				else{
					fprintf(g,"0 0\n");
					continue;
				}
			}
		}

		euclid(a,b,&d,&x,&y);

		long long lim=2000000000;

		if(c%d==0){
			long long x1=x*(c/d);
			long long y1=y*(c/d);
			if(abs((double)x1)<=lim && abs((double)y1)<=lim){
				fprintf(g,"%lld %lld\n",x1,y1);
				continue;
			}

			long long k1,k2,k3,k4;
			
			if(b>0){
				k1=(-lim*d-c*x)/b;
				k2=(lim*d-c*x)/b;
			}
			else{
				k2=(-lim*d-c*x)/b;
				k1=(lim*d-c*x)/b;
			}

			if(a>0){
				k4=(lim*d+c*y)/a;
				k3=(-lim*d+c*y)/a;
			}
			else{
				k3=(lim*d+c*y)/a;
				k4=(-lim*d+c*y)/a;
			}

			long long k;
			if(k3<=k2)
				k=k3;
			else
				k=k4;

			x=x*(c/d)+k*(b/d);
			y=y*(c/d)-k*(a/d);

			fprintf(g,"%lld %lld\n",x,y);
		}
		else{
			fprintf(g,"0 0\n");
		}

	}

	fclose(g);
	fclose(f);
	return 0;
}