Mai intai trebuie sa te autentifici.

Cod sursa(job #2240876)

Utilizator timpaladeTimotei Palade timpalade Data 14 septembrie 2018 12:26:26
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
//
//  EuclidExtended.cpp
//  InfoArena
//
//  Created by Tim Palade on 9/14/18.
//  Copyright © 2018 Tim Palade. All rights reserved.
//

#include <stdio.h>

using namespace std;

void euclidExtended(int a, int b, int *x, int *y, int *d) {
    
    if (b == 0) {
        *d = a;
        *x = 1;
        *y = 0;
    }
    else {
        int x0, y0;
        euclidExtended(b, a%b, &x0, &y0, d);
        *x = y0;
        *y = x0 - (a/b) * y0;
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int T;
    
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    
    scanf("%d", &T);
    for (; T; --T)
    {
        int a, b, c, x, y, d;
        scanf("%d %d %d", &a, &b, &c);
        
        euclidExtended(a, b, &x, &y, &d);
        //printf("x = %d | y = %d | gcd = %d\n", x, y, d);
        //assert(x * a + y * b == d);
        
        if (c % d != 0) { //no solutions
            //write 0 to the file
            printf("%d %d\n", 0, 0);
        }
        else { //has solutions
            // a * alpha + b * beta = c
            // alpha = (c/d) * x
            // beta = (c/d) * y
            int m = c / d;
            int alpha = m * x;
            int beta = m * y;
            
            printf("%d %d\n", alpha, beta);
            //assert(alpha * a + beta * b == c);
        }
    }
    
    return 0;
}