Cod sursa(job #2930940)

Utilizator TheEpicWipedCreaVlad Chirita Alexandru TheEpicWipedCrea Data 29 octombrie 2022 21:24:42
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

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

void euclid_ceva(long long a,long long b,long long &x, long long &y){
	if(b==0){
		x=1;
	    y=0;
	}
	else{
		euclid_ceva(b,a%b,x,y);
		long long aux=x;
		x=y;
		y=aux-y*(a/b);
	}
}


int main(){
    int q;
    long long a,b,c;
    in>>q;
    for(int z=1;z<=q;z++){
        in>>a>>b>>c;
        long long ca=a,cb=b;
        while(cb!=0){
            long long aux=ca%cb;
            ca=cb;
            cb=aux;
        }
        long long cmmd=ca;
        long long s1=0,s2=0;
        euclid_ceva(a,b,s1,s2);
        if(c%cmmd==0){
            long long r=c/cmmd;
            s1*=r;
            s2*=r;
            out<<s1<<" "<<s2<<'\n';
        }
        else{
            out<<"0 0"<<'\n';
        }
    }
}