Cod sursa(job #3277651)

Utilizator TomaVVrinceanu Toma TomaV Data 17 februarie 2025 10:46:39
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
using namespace std;
ifstream cin("euclid3.in");
ofstream cout("euclid3.out");
int a,b,r,n1,m1,n2,m2,m,n,c,c1,cnt,rez,T,r1;
int main()
{
    cin>>T;
    for(int i=1; i<=T; i++)
    {
        cin>>a>>b>>rez;
        cnt=1;
        if(b==0)
        {
            if(rez%a==0)
                cout<<rez/a<<' '<<0<<endl;
            else cout<<0<<' '<<0<<endl;
        }
        else
        {
        c1=a/b;
        r1=a%b;
        if(r1==0)
        {
            m=rez/b;
            n=(1-a/b)*m;
            cout<<m<<' '<<n<<endl;
        }
        while(b != 0)
        {
            r=a%b;
            c=a/b;

            if(cnt==1)
            {
                m1=1;
                n1=-c;
            }
            else if(cnt==2)
            {
                m2=-c;
                n2=1+c1*c;
            }
            else
            {
                m=m1-m2*c;
                n=n1-n2*c;
                m1=m2;
                n1=n2;
                m2=m;
                n2=n;
            }
            a=b;
            b=r;
            cnt++;
        }
        if(rez%a!=0)
            cout<<0<<' '<<0<<endl;
        else
        {
            m1=rez/a*m1;
            n1=rez/a*n1;
            cout<<m1<<' '<<n1<<endl;
        }
        }
    }
    return 0;
}