Untitled

 avatar
ahmedsalah7
plain_text
a month ago
2.1 kB
2
Indexable
Gyms
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define AboTaha_on_da_code ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define X first
#define Y second

const int dx[8]={0, 0, 1, -1, 1, -1, -1, 1};
const int dy[8]={1, -1, 0, 0, 1, -1, 1, -1};
const double EPS = 1e-8;
const int mod = 1e9+7; // 1e9+7, 998244353
const int phi = 1e9+6; // 1e9+7, 998244353
// BEFORE coding are you sure you understood the statement correctly?
// PLEASE do not forget to read the sample explanation carefully.
// WATCH out for overflows & RTs in general.
// TEST your idea or code on the corner cases.
// ANALYZE each idea you have thoroughly.

int valid[10];
void pre() {
    int a[10]{};
    for (int i = 1; i < 10; i++) a[i-1] = i*i;
    for (int msk = 1; msk < (1<<9); msk++) {
        int sm = 0;
        for (int i = 0; i < 9; i++) {
            if (msk>>i&1) sm+=a[i];
        }
        int sq = sqrt(sm);
        if (sq*sq == sm) valid[__builtin_popcount(msk)] = msk;
    }
}

void burn(int tc) {
    ll n; cin >> n;
    ll ans[10]{};
    for (int i = 1; i < 8; i++) {
        if (n%i == 0) {
            ll sq = sqrtl(n/i);
            if (sq*sq != n/i) continue;
            for (int j = 1; j < 10; j++) {
                if (valid[i]>>(j-1)&1) ans[j] = n/i;
            }
            for (int j = 1; j < 10; j++) cout << ans[j] << ' ';
            return;
        }
    }
    ll sq = sqrtl(n);
    ans[3] = ans[4] = n-sq*sq;
    ans[5] = 2*sq*sq-n;
    for (int j = 1; j < 10; j++) cout << ans[j] << ' ';
}

int main()
{
    AboTaha_on_da_code

//    freopen("points.in", "r", stdin);
//    freopen("output.txt", "w", stdout);

    int T = 1; cin >> T;

    pre();

    for (int i = 1; i <= T; i++) {
//        cout << "Case " << i << ": ";
        burn(i);
        cout << '\n';
    }
    return (0-0);
}
Leave a Comment