Cod sursa(job #3250198)

Utilizator n6v26rDedu Razvan Matei n6v26r Data 19 octombrie 2024 17:00:15
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <stdio.h>
#include <iostream>

std::pair<int, int> euclid(int a, int b){
  if(b==0){
    return std::make_pair(1, 0);
  }
  auto [x, y] = euclid(b, a%b);
  return std::make_pair(y, x - a / b * y);
}

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

int main(){
  FILE *fin = fopen("euclid3.in", "r");
  FILE *fout = fopen("euclid3.out", "w");
  int n;
  fscanf(fin, "%d", &n);
  for(int i=0; i<n; i++){
    int a, b, c;
    fscanf(fin, "%d%d%d", &a, &b, &c);
    auto [x, y] = euclid(a, b);
    int cmmdc = gcd(a, b);
    if(c%cmmdc) {x = y = 0;}
    else{
      x*=(c/cmmdc);
      y*=(c/cmmdc);
    }
    fprintf(fout, "%d %d\n", x, y);
  }
  fclose(fin);
  fclose(fout);
  return 0;
}