Cod sursa(job #3357260)

Utilizator tomescuioanacasianaTomescu Ioana-Casiana tomescuioanacasiana Data 7 iunie 2026 20:35:16
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>

long long invers_modular(long long a, long long b, long long *x, long long *y)
{
  if(b == 0){
    *x = 1;
    *y = 0;
    return a;
  }
  long long X, Y, d;
  d = invers_modular(b, a % b, &X, &Y);
  *x = Y;
  *y = X - (a / b) * Y;
  return d;
}

void euclid_extins(long long a, long long b, long long c, FILE *fout){
  long long d, x, y;
  d = invers_modular(a, b, &x, &y);
  if(c % d != 0){
    fprintf(fout, "0 0\n");
  }
  else{
    long long X = x *(c / d);
    long long Y = y * (c / d);
    fprintf(fout, "%lld %lld\n", X, Y);
  }
}

int main(void)
{
  FILE *fin = fopen("euclid3.in", "r");
  FILE *fout = fopen("euclid3.out", "w");
  int t;
  fscanf(fin, "%d", &t);
  int i;
  long long a, b, c;
  for(i = 0; i < t; i++){
    fscanf(fin, "%lld %lld %lld", &a, &b, &c);
    euclid_extins(a, b, c, fout);
  }
  fclose(fin);
  fclose(fout);
  return 0;
}