Cod sursa(job #2765938)

Utilizator AACthAirinei Andrei Cristian AACth Data 30 iulie 2021 13:56:01
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.47 kb
#include <bits/stdc++.h>
void nos()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}
namespace BasicMath{

    //Euler fuction in O(sqrt(n))
    int phi(int n)
    {
        if(n == 1)
            return 0;
        int result = n;
        for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
        if (n > 1)
        result -= result / n;
        return result;
    }
    //Divisors
    std::vector < std::pair < int ,int > > Divisors(int n)
    {
        //{baza, exponent}
        std::vector < std::pair< int , int> > ans;
        if(n % 2 == 0)
        {
            int exp = 0;
            while(n % 2 == 0)
            {
                n /= 2;
                ++exp;
            }
            ans.push_back({2,exp});
        }
        int d = 3;
        while(n!=1)
        {
            if(n % d == 0)
            {
                int exp = 0;
                while(n % d == 0)
                {
                    n /= d;
                    exp++;
                }
                ans.push_back({d,exp});
            }
            if(d * d > n)
                break;
            d+=2;
        }
        if(n != 1)
            ans.push_back({n,1});

        return ans;
    }
    int fastpowsimple(int base,int exp,int MOD)
    {
        int ans = 1;
        while(exp)
        {
            if(exp & 1)
                ans*=base,ans%=MOD;
            base *= base;
            base %= MOD;
            exp >>= 1;
        }
        return ans;
    }
    int gcd(int a,int b)
    {
        while(b)
        {
            a %= b;
            std::swap(a,b);
        }
        return a;
    }
    int ExtendedEuclid(int a, int b, int &x, int &y)
    {
        //a*x + b*y = (gcd(a,b))
        if(a == 0)
        {
            x = 0; y = 1;
            return b;
        }
        int x1,y1;
        int d = ExtendedEuclid(b%a,a,x1,y1);
        x = y1 - (b / a) * x1;
        y = x1;
        return d;
    }
}
std::ifstream f("euclid3.in");
std::ofstream g("euclid3.out");
int32_t main()
{
    
    nos();
    int teste;
   f>>teste;
   while(teste --)
   {
    int a,b,c;
    f>>a>>b>>c;
    int x,y;
    int d = BasicMath::ExtendedEuclid(a,b,x,y);
    //std::cout<<d<<"asta e d\n";
    if(c%d != 0)
       g<<"0 0\n";
    else
        g<<x * (c/d)<<' '<<y*(c/d)<<'\n';
   }
}