Pagini recente » Cod sursa (job #3357650) | Cod sursa (job #3358219) | Cod sursa (job #3358228) | Cod sursa (job #3358131) | Cod sursa (job #3358328)
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
if(b==0)return a;
return gcd(b,a%b);
}
void extGCD(int a, int b, int &va1, int &va2){
if(b==0){
va1=1;
va2=0;
return;
}
int v1,v2;
extGCD(b,a%b,v1,v2); // v1*b + v2*(a-kb)=x a%b = a-kb v1*b + v2*a
int k=a/b;
va1=v2;
va2=v1-k*v2;
}
void solve(){
int a,b,c;cin>>a>>b>>c;
bool isW=false;
if(a<b){swap(a,b);isW=true;}
int gc=gcd(a,b);
if(c%gc!=0){cout<<"0 0\n";return;}
int mult=c/gc;
int v1,v2;
extGCD(a,b,v1,v2);
if(isW){
swap(v1,v2);
}
cout<<v1*mult<<' '<<v2*mult<<'\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
freopen("euclid3.in","r",stdin);
freopen("euclid3.out","w",stdout);
int Q;cin>>Q;
while(Q--){
solve();
}
}