Cod sursa(job #2241766)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 16 septembrie 2018 22:09:48
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <assert.h>

using LL = long long;
using ULL = int long long;

const std::string _problemName = "euclid3";

namespace std {
std::ifstream fin(_problemName + ".in"); 
std::ofstream fout(_problemName + ".out"); 
}

#define cin fin
#define cout fout

void euclid(int& d, int& x, int& y, int a, int b) {
    if (b == 0) {
        d = a;
        x = 1;
        y = 0;
        return;
    }

    int x1, y1;
    euclid(d, x1, y1, b, a % b);

    // b * x1 + (a % b) * y1 == d
    // a * x + b * y == d

    // b * x1 + (a % b) * y1 == a * x + b * y
    // b * (x1 - y) + (a - (a / b) * b) * y1 - a * x == 0
    // b * (x1 - y) + a * y1 - b * y1 * (a / b) - a * x == 0
    // b * (x1 - y - y1 * (a / b)) + a * (y1 - x) == 0
    
    x = y1;
    y = x1 - y1 * (a / b);
}

std::pair<int, int> solveEuclid(int a, int b, int c) {
    int d, x, y;
    euclid(d, x, y, a, b);

    if (c % d != 0) {
        return std::make_pair(0, 0);
    }

    x *= c / d;
    y *= c / d;

    return std::make_pair(x, y);
}

int main() {

    int t;
    std::cin >> t;

    while (t--) {
        int a, b, c;
        std::cin >> a >> b >> c;

        auto sol = solveEuclid(a, b, c);
        std::cout << sol.first << ' ' << sol.second << '\n';
    }

    return 0;
}