Cod sursa(job #3146389)

Utilizator GrigMihaiGrigore Mihai GrigMihai Data 20 august 2023 19:16:24
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
using namespace std;

ifstream in("euclid3.in");
ofstream out("euclid3.out");



int main()
{
    int n;
    in>>n;

    while(n)
    {
        int a, b, c, d, x=1, y=1;
        in>>a>>b>>c;

        if(a%b==0)
        {
            d=b;
            x=0;
            y=1;
        }
        else if(b%a==0)
        {
            d=a;
            x=1;
            y=0;
        }
        else
        {
            int xa=1, ya=0, xb=0, yb=1;

            while(a%b!=0)
            {
                d=a%b;
                x=xa-(a/b)*xb;
                y=ya-(a/b)*yb;

                xa=xb;
                ya=yb;
                xb=x;
                yb=y;
                a=b;
                b=d;
            }
        }

        if(c%d!=0)
            out<<"0 0\n";
        else
            out<<x*(c/d)<<" "<<y*(c/d)<<'\n';

        n--;
    }

    return 0;
}