Cod sursa(job #2388617)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 26 martie 2019 11:32:32
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
using namespace std;
long long i, n, X1, X2, Y1, Y2, x, y, rest1, rest2, rest, d, val, cat;
int cmmdc(int a, int b)
{
    int d = a, i = b, r = d % i;
    while(r != 0)
    {
        d = i;
        i = r;
        r = d % i;
    }
    return i;
}
int main()
{
    ifstream f("euclid3.in");
    ofstream g("euclid3.out");
    f >> n;
    for(i = 1; i <= n; i ++)
    {
        f >> rest1 >> rest2 >> d;
        val = cmmdc(rest1, rest2);
        X1 = 1;
        X2 = 0;
        Y1 = 0;
        Y2 = 1;
        if(d % val != 0)
        {
            g << "0 0" << "\n";
            continue;
        }
        while(rest1 % rest2 != 0)
        {
            cat = rest1 / rest2;
            rest = rest1 % rest2;
            rest1 = rest2;
            rest2 = rest;
            x = X1 - cat * X2;
            y = Y1 - cat * Y2;
            X1 = X2;
            X2 = x;
            Y1 = Y2;
            Y2 = y;
        }
        g << X2 * (d / val) << " " << Y2 * (d / val) << "\n";
    }
    return 0;
}