Cod sursa(job #1744529)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 19 august 2016 22:08:22
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <algorithm>
#include <string>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <cassert>
#include <ctime>
using namespace std;
 
#ifdef INFOARENA
#define TEST 0
#else
#define TEST 1
#endif

struct Input {
    long long a, b, c;
};

class ExtendedEuclid {
public:
    void Solve(long long a, long long b, long long &d, 
               long long &x, long long &y) {
        if (b == 0) {
            x = 1;
            y = 0;
            d = a;
            return;
        } else {
            long long x0, y0;
            Solve(b, a%b, d, x0, y0);
            x = y0;
            y = x0 - (a/b) * y0;
        }
    }
};
 
int main() {

    vector<Input> input;

    if (TEST) {
        input.push_back({24,15,147});
        input.push_back({24,16,104});
        input.push_back({2,4,5});
    } else {
        freopen("euclid3.in","r",stdin);
        freopen("euclid3.out","w",stdout);
        int num_tests;
        scanf("%d", &num_tests);
        for (int i = 0; i < num_tests; ++i) {
            long long a,b,c;
            scanf("%lld %lld %lld", &a, &b, &c);
            input.push_back({a,b,c});
        }
    }

    ExtendedEuclid *instance = new ExtendedEuclid();

    for (const Input& in : input) {
        long long x, y, d;
        instance->Solve(in.a, in.b, d, x, y);
        if (in.c % d == 0) {
            printf("%lld %lld\n", (in.c / d) * x, (in.c / d) * y);
        } else {
            printf("0 0\n");
        }
    }

    return 0;
}