Cod sursa(job #2959980)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 3 ianuarie 2023 12:47:22
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <bits/stdc++.h>
using namespace std;

template<typename T> struct Result{
  T x,y,z;
  void euclid(T a, T b){
    if(b==0){
      x=1;
      y=0;
      z=a;
    }else{
      /**

      a*x2+b*y2=g
      b*x+(a-b*c)*y=g
      b*(y2-x+c*y)+a*(x2-y)

      **/
      euclid(b,a%b);
      T x2=y,y2=x-(a/b)*y;
      x=x2;
      y=y2;
    }
  }
  void makepozi(T a,T b){
    assert(a*x+b*y==z);
    assert(z);
    T dx=b;
    T dy=-a;
    assert(a*(x+dx)+b*(y+dy)==z);
    /*
    if(dx<0){
      dx*=-1;
    }
    if(dx>=1){
      if(x<0){
        while(x<0){
          x+=dx;
          y+=dy;
        }
      }
    }else{
      assert(dx==0);
      x=0;
    }
    assert(a*x+b*y==z);
    assert(x>=0);*/
    /**
    a*x+b*y=z
    a*x2+b*y2=z

    a*(x-x2)+b*(y-y2)=0
    a*(x-x2)=b*(y2-y)

    a*dx=b*-dy


    **/
  }
};
typedef long long ll;
/*
#ifdef ONPC
const int N=10000;
#else
const int N=31623776;
#endif // ONPC
bool isprime[N];
vector<int> p;
*/
int main(){
#ifdef ONPC
  freopen("input.txt","r",stdin);
  ///freopen("output.txt","w",stdout);
#else
freopen("euclid3.in","r",stdin);
freopen("euclid3.out","w",stdout);
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#endif // ONPC

  Result<ll> it;
  int t;
  cin>>t;
  while(t--){
    ll a, b, c;
    cin>>a>>b>>c;
    it.euclid(a,b);
    if(c%it.z){
      cout<<"0 0\n";
      continue;
    }
    it.makepozi(a,b);
    it.x*=(c/it.z);
    it.y*=(c/it.z);
    cout<<it.x<<" "<<it.y<<"\n";
  }
  exit(0);

  /*isprime[2]=1;
  for(int i=3;i<N;i+=2)isprime[i]=1;
  for(int i=3;i*i<N;i+=2)if(isprime[i]){
    for(int j=i*i;j<N;j+=2*i){
      isprime[j]=0;
    }
  }
  for(int i=0;i<N;i++){
    if(isprime[i]){
      p.push_back(i);
    }
  }
  map<ll,vector<ll>> mpdivis;
  int q;
  cin>>q;
  while(q--){
    ll number,sc;
    cin>>number>>sc;
    if(!mpdivis.count(sc)){
      ll ini=sc;
      for(auto&dv:p){
        if(sc%dv==0){
          while(sc%dv==0)sc/=dv;
          mpdivis[ini].push_back(dv);
        }
      }
      if(sc>1)mpdivis[ini].push_back(sc);
      sc=ini;
    }
    vector<ll> divis=mpdivis[sc];
    int k=(int)divis.size();

    if(1){
      cout<<" ---> ";
      for(auto&x:divis){
        cout<<x<<" ";
      }
      cout<<"\n";
    }
  }
*/
}
/**

**/