Cod sursa(job #2710637)

Utilizator marius004scarlat marius marius004 Data 22 februarie 2021 20:07:17
Problema Invers modular Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("euclid3.in");
ofstream g("euclid3.out");

// a * x + b * y = d care este egal cu cmmdc(a, b)
int cmmdc(int a, int b, int& x, int& y) {

    if(b == 0) {

        /**
                ecuatia a * x + b * y = d devine
                        a * x + 0 * y = a care devine
                        a * x         = a
                => x = 1 iar y este orice valoare(in acest caz o consider 0)
         **/

        x = 1;
        y = 0;

        return a;
    }

    int xa, ya;
    int d = cmmdc(b, a % b, xa, ya);

    /**
        a * x + b * y = d
        Also d = cmmdc(b, a % b, xa, ya)
        => a * x + b * y === b * xa + (a % b) * ya care sunt egale cu d

        TEOREMA IMPARTIRII CU REST:
           a = (a / b) * b + (a % b)
           => a % b = a - (a / b) * b;


        DECI ecuatia a * x + b * y === b * xa + (a % b) * ya devine:
            a * x + b * y === b * xa + ( a - (a / b)* b ) * ya
           a * x + b * y  === b * xa + a * ya - (a / b) * b * ya

        <=> a(x - ya) + b(y - xa + (a / b) * ya ) = 0

         => x = ya si y = -1 * ( - xa + (a / b) * ya  )
         => y = xa - (a / b) * ya
     **/

    x = ya;
    y = xa - (a / b) * ya;

    return d;
}

int main() {

    int t;

    f >> t;

    while(t--) {

        int a, b, c;
        f >> a >> b >> c;

        /**
                a * x + b * y = d care este egal cu cmmdc(a, b)

                acum trebuie sa gasim:
                    a * x + b * y = c

                cazul 1: daca c % d != 0
                    atunci asta inseamna ca ecuatia nu are solutii
                cazul 2: daca c % d == 0
                    atunci putem sa inmultim toata ecuatia cu (c/d)

                    ecuatia devine:
                            1) a * [x*(c/d)] + b * [y*(c/d)] = d*(c/d)
                            2) a * [x*(c/d)] + b * [y*(c/d)] = c

                    din 2 rezulta ca solutia ecuatiei este perechea { ( x*(c/d), y*(c/d) ) }
         **/

        int x, y;
        int d = cmmdc(a, b, x, y);

        if(c % d == 0)
            g << x * (c / d) << ' ' << y * (c / d) << '\n';
        else
            g << 0 << ' ' << 0 << '\n';
    }

    return 0;
}