Cod sursa(job #2643670)

Utilizator De_Azi_Ne_DopamAlex Ardelean De_Azi_Ne_Dopam Data 20 august 2020 20:28:25
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;
int cmmdc(int a,int b)
{
 int r;
 while(b)
 {
  r=a%b;
  a=b;
  b=r;
 }
 return a;
}
void extins(int a,int b,int &x1,int &y1,int &d)
{
 if(b==0)
 {
  x1=1;
  y1=0;
  d=a;
 }
 else
 {
  int x2,y2;
  extins(b,a%b,x2,y2,d);
  x1=y2;
  y1=x2-(a/b)*y2;
 }
}
int main()
{
#ifdef HOME
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
#endif // HOME
#ifndef HOME
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,i,a,b,c,x1,y1,d,x;
    cin>>n;
    for(i=1;i<=n;i++)
    {
     cin>>a>>b>>c;
     x=cmmdc(a,b);
     if(c%x!=0)
     cout<<"0 0\n";
     else
     {
      extins(a,b,x1,y1,d);
      cout<<x1*(c/d)<<" "<<y1*(c/d)<<'\n';
     }
    }
    return 0;
}