Cod sursa(job #2238928)

Utilizator al3xionescuIonescu Alexandru al3xionescu Data 8 septembrie 2018 13:57:02
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
 
using namespace std;
 
ifstream f("euclid3.in");
ofstream g("euclid3.out");
 
typedef struct pairs{ int x; int y; } pairs;
 
int cmmdc(int a, int b){
    if (a == 0 || b == 0)
        return a + b;
    if (a > b) return cmmdc(a % b, b);
    else return cmmdc(a, b % a);
}
 
pairs euclid_extended(int a, int b){
    pairs result;
    if (b == 1){
        result.x = 0;
        result.y = -1;
    } else if (a == 1){
        result.x = 1;
        result.y = 0;
    } else {
        int d, c;
        pairs rez;
        if(a > b){
            d = a / b;
            c = a % b;
            result = euclid_extended(b, c);
            rez.x = - result.y;
            rez.y = - (result.x + d * result.y);
        } else {
            d = b / a;
            c = b % a;
            result = euclid_extended(a, c);
            rez.y = result.y;
            rez.x = result.x + d * result.y;
        }
        return rez;
    }
 
    return result;
}
 
void solve(int a, int b, int c){
    int cm = cmmdc(abs(a), abs(b));
    if (c % cm != 0)
        g << "0 0\n";
    else{
        a = a / cm;
        b = b / cm;
        c = c / cm;
        pairs p = euclid_extended(abs(a), abs(b));
        if (p.x != 0)
            p.x = (a / abs(a)) * p.x;
        if (p.y != 0)
            p.y = (b / abs(b)) * p.y;
        g << p.x * c << " " << - p.y * c << '\n';
    }
}
 
int main() {
    int n, a, b, c;
    f >> n;
    for(int i = 1; i <= n; i++){
        f >> a >> b >> c;
        solve(a, b, c);
    }
    f.close();
    g.close();
    return 0;
}