Cod sursa(job #2812958)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 5 decembrie 2021 15:14:39
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
#define LL long long

using namespace std;

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

LL teste, a, b, cmmdc, target;

LL solX, solY, k;
LL x[70], y[70], s[70];
void euclidExtins(LL a, LL b){

    ///targetul meu:
    /// a * x[i] + b * y[i] = s[i];

    /// rest = s[i-2] % s[i-1]
    /// cat  = s[i-2] / s[i-1]
    ///s[i] = rest
    ///x[i] = x[i-2] - cat * x[i-1]
    ///y[i] = y[i-2] - cat * y[i-1]

    k = 3;
    s[1] = a, s[2] = b;
    x[1] = 1, y[1] = 0;
    x[2] = 0, y[2] = 1;

    LL rest, cat;
    while(s[k-2] % s[k-1] != 0){

        rest = s[k-2] % s[k-1];
        cat  = s[k-2] / s[k-1];
        s[k] = rest;
        x[k] = x[k-2] - cat * x[k-1];
        y[k] = y[k-2] - cat * y[k-1];
        k++;
    }
    k--;
    cmmdc = s[k];
    solX  = x[k];
    solY  = y[k];
}

int main (){
    int teste;
    fin >> teste;
    while(teste--){
        fin >> a >> b >> target;
        euclidExtins(a, b);

        if(target % cmmdc != 0)
            fout << "0 0\n";
        else
            fout << target / cmmdc * solX << " " << target / cmmdc * solY << "\n";
    }
    return 0;
}