Cod sursa(job #2800835)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 14 noiembrie 2021 07:05:33
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using cd = complex<double>;

constexpr ll mod = 1e9 + 7, maxn = 3e5 + 10;

pair<ll, ll> euclid_extins(ll x, ll y);

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

    int t;
    f >> t;
    while (t--) {
        ll x, y, z, a, b;
        f >> x >> y >> z;
        tie(a, b) = euclid_extins(x, y);
        ll G = a * x + b * y;
        if (z % G)
            g << 0 << ' ' << 0 << '\n';
        else
            g << (a * (z / G)) << ' ' << (b * (z / G)) << '\n';
    }
    return 0;
}

pair<ll, ll> euclid_extins(ll x, ll y) {
    ll g = 1;
    while (x % 2 == 0 && y % 2 == 0) x /= 2, y /= 2, g *= 2;
    ll u = x, v = y, a = 1, b = 0, c = 0, d = 1;
    do {
        for (int i = 0; i < 2; ++i) {
            while (u % 2 == 0) {
                u /= 2;
                if (a % 2 == 0 && b % 2 == 0)
                    a /= 2, b /= 2;
                else
                    a = (a + y) / 2, b = (b - x) / 2;
            }
            swap(a, c);
            swap(b, d);
            swap(u, v);
        }
        if (u >= v)
            u -= v, a -= c, b -= d;
        else
            v -= u, c -= a, d -= b;
    } while (u != 0);
    return make_pair(c, d);
}