Cod sursa(job #3281682)

Utilizator Robert_NicuNicu Robert Cristian Robert_Nicu Data 3 martie 2025 11:03:46
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;

ofstream fout("euclid3.out");

int t, a, b, c, d, x, y;

char c1;

bool GetInt(int &x){

    if(c1 == -1)

        return false;

    c1 = getchar();

    while(c1 == ' ')

        c1 = getchar();

    if(c1 == -1)

        return false;

    int sgn = 1;

    x = 0;

    if(c1 == '-')

        sgn = -1;

    else x = c1 - '0';

    c1 = getchar();

    while(isdigit(c1)){

        x = x * 10 + (c1 - '0');

        c1 = getchar();

    }

    x *= sgn;

    return true;

}

void modinv(int a, int b, int &d, int &x, int &y){

    if(b == 0)

        d = a, x = 1, y = 0;

    else{

        int x1, y1;

        modinv(b, a % b, d, x1, y1);

        x = y1;

        y = x1 - a / b * y1;

    }

}

int32_t main(){

    freopen("euclid3.in", "r", stdin);

    GetInt(t);

    while(t--){

        GetInt(a);

        GetInt(b);

        GetInt(c);

        modinv(a, b, d, x, y);

        if(c % d != 0)

            fout << "0 0\n";

        else fout << (x * c) / d << " " << (y * c) / d << "\n";

    }

}