Cod sursa(job #2916830)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 1 august 2022 18:50:03
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#define int long long

using namespace std;

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

const int MAX_Q = 105;
int qcnt, startX, startY, target;

int cmmdc, solX, solY;
int cnt, x[100], y[100], s[100];
void euclidExtins(){
    /**
    My goal:
    startX * x[i] + startY * y[i] = s[i]


    Initialize:
    s[1] = startX
    x[1] = 1
    y[1] = 0

    s[2] = startY
    x[2] = 0
    y[2] = 1


    Recurrence:
    s[i] = s[i-2] % s[i-1]
    x[i] = x[i-2] - x[i-1] * (s[i-2] / s[i-1])
    y[i] = y[i-2] - y[i-1] * (s[i-2] / s[i-1])
    **/

    if(startX == 0){
        cmmdc = startY;
        solX = 0;
        solY = 1;
        return;
    }

    if(startY == 0){
        cmmdc = startX;
        solX = 1;
        solY = 0;
        return;
    }

    cnt = 3;
    s[1] = startX, x[1] = 1, y[1] = 0; /// startX * 1 + startY * 0 = startX
    s[2] = startY, x[2] = 0, y[2] = 1; /// startX * 0 + startY * 1 = startY
    while(s[cnt-2] % s[cnt-1] != 0){
        s[cnt] = s[cnt-2] % s[cnt-1];
        x[cnt] = x[cnt-2] - x[cnt-1] * (s[cnt-2] / s[cnt-1]);
        y[cnt] = y[cnt-2] - y[cnt-1] * (s[cnt-2] / s[cnt-1]);
        cnt++;
    }
    cnt--;
    cmmdc = s[cnt];
    solX = x[cnt];
    solY = y[cnt];
    return;
}

signed main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>qcnt;
    while(qcnt--){
        fin>>startX>>startY>>target;
        euclidExtins();

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