Cod sursa(job #3323113)

Utilizator Andrei_PanaAndrei Pana Andrei_Pana Data 17 noiembrie 2025 10:03:53
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.54 kb
#include <fstream>
using namespace std;

ifstream cin("euclid3.in");
ofstream cout("euclid3.out");

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,a,b,c;
  long long x,y,d,k;

  cin>>t;
  while(t--){
    cin>>a>>b>>c;
    d=x=y=0;
    euclid(a,b,&d,&x,&y);
    k=c/d;
    if(c%d!=0){
      k=0;
    }
    x*=k;
    y*=k;
    cout<<x<<" "<<y<<"\n";
  }

  return 0;
}