Cod sursa(job #3323112)

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

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

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

long long gcd(long long a,long long b){
  while(b){
    int r=a%b;
    a=b;
    b=r;
  }
  return a;
}

int main(){
  int t,a,b,c;
  long long x,y;

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

  return 0;
}