IATI 2017 SHOPPING или решение длинного Диофантова ур-я.

#pragma GCC optimize("O2")
#define NDEBUG
#include <bits/stdc++.h>
using namespace std;

using Int   = long long;
using Real  = long double;
using Char  = unsigned char;
using Bool  = unsigned char;

const Int INT_INF   = 2E18;
const Int BOUND     = 1E9;
const Int N         = 2E5;

Int extended_gcd(Int a, Int & x, Int b, Int & y)
{
    if (a == 0)
    {
        x = 0;
        y = 1;
        return b;
    }
    Int x1, y1, g;
    g = extended_gcd(b % a, x1, a, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return g;
}

Int floor_div(Int a, Int b)
{
    if (b < 0)
    {
        a = -a;
        b = -b;
    }
    if (a >= 0)
    {
        return a / b;
    }
    return (a - b + 1) / b;
}

Int ceil_div(Int a, Int b)
{
    if (b < 0)
    {
        a = -a;
        b = -b;
    }
    if (a >= 0)
    {
        return (a + b - 1) / b;
    }
    return a / b;
}

void solve_diofant(Int a, Int & x, Int b, Int & y, Int c)
{
    Int g = extended_gcd(a, x, b, y);

    Int x0 = x * c;
    Int y0 = y * c;
    Int dx = (b / g);
    Int dy = -(a / g);

    /// x = x0 + k * dx
    /// y = y0 + k * dy

    Int min_k = -INT_INF, max_k = INT_INF;

    /// x0 + k * dx >= -BOUND
    /// y0 + k * dy >= -BOUND
    if (dx > 0)
    {
        min_k = max(min_k, ceil_div(-x0 - BOUND, dx));
    }
    else
    {
        max_k = min(max_k, floor_div(-x0 - BOUND, dx));
    }
    if (dy > 0)
    {
        min_k = max(min_k, ceil_div(-y0 - BOUND, dy));
    }
    else
    {
        max_k = min(max_k, floor_div(-y0 - BOUND, dy));
    }

    /// x0 + k * dx <= BOUND
    /// y0 + k * dy <= BOUND
    if (dx > 0)
    {
        max_k = min(max_k, floor_div(BOUND - x0, dx));
    }
    else
    {
        min_k = max(min_k, ceil_div(BOUND - x0, dx));
    }
    if (dy > 0)
    {
        max_k = min(max_k, floor_div(BOUND - y0, dy));
    }
    else
    {
        min_k = max(min_k, ceil_div(BOUND - y0, dy));
    }

    assert(min_k <= max_k);

    Int k = (min_k + max_k) / 2;

    x = x0 + k * dx;
    y = y0 + k * dy;
}

Int answer[N];
int a[N];

const Int L = 20;

int t[L][N];
Int bin_log[N];

void build()
{
    bin_log[1] = 0;
    for (Int i = 2; i < N; ++i)
    {
        bin_log[i] = bin_log[i / 2] + 1;
    }

    fill(t[0], t[0] + N * L, 0);
    copy(a, a + N, t[0]);

    for (Int i = 1; i < L; ++i)
    {
        for (Int j = 0; j + (1LL << i) <= N; ++j)
        {
            t[i][j] = __gcd(t[i - 1][j], t[i - 1][j + (1LL << (i - 1))]);
        }
    }
}

Int range_gcd(Int l, Int r)
{
    Int i = bin_log[r - l];
    return __gcd(t[i][l], t[i][r - (1LL << i)]);
}

void recursive_solve(Int l, Int r, Int c)
{
    if (r - l == 1)
    {
        answer[l] = c;
        return;
    }
    Int m = (l + r) / 2;
    Int g1 = range_gcd(l, m);
    Int g2 = range_gcd(m, r);
    Int x, y;

    solve_diofant(g1, x, g2, y, c);

    recursive_solve(l, m, x);
    recursive_solve(m, r, y);
}


void solve()
{
    Int n, c, g = 0;
    cin >> n;

    fill(a, a + N, 0);

    for (Int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }

    build();

    g = range_gcd(0, n);

    cin >> c;

    if (c % g)
    {
        cout << "No solutions\n";
        return;
    }

    recursive_solve(0, n, c / g);

    for (Int i = 0; i < n; ++i)
    {
        cout << answer[i] << ' ';
    }
    cout << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    Int tests;
    cin >> tests;

    while (tests--)
    {
        solve();
    }

    return 0;
}