Cod sursa(job #1149553)

Utilizator teoionescuIonescu Teodor teoionescu Data 22 martie 2014 00:02:49
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<queue>
#define abs(x) ((x>0)?(x):(-(x)))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define ll long long
using namespace std;
ifstream in("euclid3.in");
ofstream out("euclid3.out");
int A[5],B[5],S[5];
int N;
int main(){
    in>>N;
    for(int i=1;i<=N;i++){
        int a,b,c;
        in>>a>>b>>c;
        A[1]=1,A[2]=0;
        B[1]=0,B[2]=1;
        S[1]=a,S[2]=b;
        while(S[2]){
            A[3]=A[1]-(S[1]/S[2])*A[2];
            B[3]=B[1]-(S[1]/S[2])*B[2];
            S[3]=A[3]*a+B[3]*b; // S[3] = A[3]*a+B[3]*b = S[1]%S[2]
            A[1]=A[2],A[2]=A[3];
            B[1]=B[2],B[2]=B[3];
            S[1]=S[2],S[2]=S[3];
        }
        if(c%S[1]==0) out<<c/S[1]*A[1]<<' '<<c/S[1]*B[1]<<'\n';
        else out<<"0 0\n";
    }
    return 0;
}