Cod sursa(job #2565753)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 2 martie 2020 16:36:51
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>

#define MAXN    1030

#define FILENAME    std::string("euclid3")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");

// A*X + B*Y == 1
int gcd(int A, int B, int &X, int &Y) {
    if (B == 0) {
        X = 1;
        Y = 0;
        return A;
    }   int ans = gcd(B, A%B, X, Y);
    int aux = Y;
    Y = X - (A/B)*Y;
    X = aux;
    return ans;
}
//  A*X + B*Y == c
//  B*p + (A%B)*q == c
//  A*X + B*p == c   <=>   A*X + c - (A%B)*q == c   <=>   A*X == (A%B)*q
//  A*q + B*Y == c   <=>   (A%B)*q + (A/B)*B*q + B*Y == c    <=>   c - B*p + B*Y + (A/B)*B*q == c
    // Y == p - (A/B)*q

int main()
{
    int T;  input >> T;
    while (T--) {
        int a, b, c;    input >> a >> b >> c;
        int x, y;       int v = gcd(a, b, x, y);
        if (c%v == 0)   output << x*(c/v) << ' ' << y*(c/v) << '\n';
        else            output << 0 << ' ' << 0 << '\n';
    }

    return 0;
}