Cod sursa(job #2635874)

Utilizator HermioneMatei Hermina-Maria Hermione Data 15 iulie 2020 19:05:27
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;
inline long long Euclid_iter(long long a, long long b)
{
    while(b!=0)
    {
        long long t;
        t = a % b;
        a = b;
        b = t;
    }
    return a;
}

void Eulid_extins(long long a, long long b, long long c, long long &x, long long &y)
{
    long long d=Euclid_iter(a,b), r=c/d;

    if(c%d)
    {
        x=y=0;
        return;
    }

    if(!a)
    {
        y=c/b;
        if(c%b==0)
            x=1;
        else
            x=y=0;
        return;
    }

     if(!b)
    {
        x=c/a;
        if(c%a==0)
            y=1;
        else
            x=y=0;
        return;
    }

    for(long long i=b; 1; i+=b)
        if(((d-i)*r)%a==0)
        {
            x = (d-i)*r/a;
            y = (c-(d-i)*r)/b;
            return;
        }
        else if(((d+i)*r)%a==0)
        {
            x = (d+i)*r/a;
            y = (c-(d+i)*r)/b;
            return;
        }
}

int main()
{
    long long n, a, b, c;
    long long x, y;

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

    f>>n;
    for(long long i = 0; i < n; i++)
    {
        f>>a>>b>>c;
        Eulid_extins(a, b, c, x, y);
        g<<x<<' '<<y<<'\n';
    }

    f.close();
    g.close();

    return 0;
}