結果
| 問題 |
No.136 Yet Another GCD Problem
|
| コンテスト | |
| ユーザー |
 smasanta
|
| 提出日時 | 2025-10-22 17:11:16 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 24,224 bytes |
| コンパイル時間 | 6,201 ms |
| コンパイル使用メモリ | 360,332 KB |
| 実行使用メモリ | 7,724 KB |
| 最終ジャッジ日時 | 2025-10-22 17:11:32 |
| 合計ジャッジ時間 | 14,225 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 3 |
| other | RE * 39 |
ソースコード
/*
यदा यदा हि धर्मस्य ग्लानिर्भवति भारत।
अभ्युत्थानमधर्मस्य तदात्मानं सृजाम्यहम्॥
*/
/*
ॐ त्र्यम्बकं यजामहे सुगन्धिं पुष्टिवर्धनम् |
उर्वारुकमिव बन्धनान्मृत्योर्मुक्षीय माऽमृतात्||
*/
//(nCr(n, r) & 1) is same as ((n & i) == i)
//For Paiwise XOR Sum, always use the zero_ct * one_ct * power of 2 concept
#include<bits/stdc++.h>
// #include <execution>
#include<ranges>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
// #pragma GCC target("avx2,sse4.2,bmi,bmi2,popcnt,lzcnt,abm,fma")
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define endl '\n'
#define sqrt sqrtl
#define _builtin_popcount __builtin_popcountll
const int MOD = 1e9 + 7;
using u64 = uint64_t;
using u128 = __uint128_t;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
// for integral types (int, long long, etc.)
template <typename T> typename enable_if<is_integral<T>::value, size_t>::type operator()(T x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(uint64_t(x) + FIXED_RANDOM);
}
// for pairs of integrals
template <typename T, typename U> size_t operator()(const pair<T, U>& p) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
uint64_t h1 = operator()(p.first);
uint64_t h2 = operator()(p.second);
// hash combine
return h1 ^ (h2 + 0x9e3779b97f4a7c15 + (h1 << 6) + (h1 >> 2));
}
};
template <typename K, typename V> using fast_map = gp_hash_table<K, V, custom_hash>;
template <typename T> using fast_set = unordered_set<T, custom_hash>;
map<u64, vector<u64>> dp_factors;
struct Node {
unique_ptr<Node> left; // Represents path for bit 0
unique_ptr<Node> right; // Represents path for bit 1
};
class Trie {
private:
unique_ptr<Node> root;
public:
Trie() {
root = make_unique<Node>();
}
void insert(int num) {
Node* node = root.get();
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (bit) {
if (node->right == nullptr) {
node->right = make_unique<Node>();
}
node = node->right.get();
} else {
if (node->left == nullptr) {
node->left = make_unique<Node>();
}
node = node->left.get();
}
}
}
int getMaxXOR(int num) {
Node* node = root.get();
int max_n = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (bit) {
if (node->left != nullptr) {
max_n |= (1 << i);
node = node->left.get();
} else {
node = node->right.get();
}
} else {
if (node->right != nullptr) {
max_n |= (1 << i);
node = node->right.get();
} else {
node = node->left.get();
}
}
}
return max_n;
}
};
int binExpo(int x, int n) {
int ans = 1;
while (n) {
if ((n & 1)) {
ans = (ans * x) % MOD;
}
x = (x * x) % MOD;
n >>= 1;
}
return ans;
}
// Calculate the n-th root of value 'a' with given precision (epsilon)
double nthRoot(double a, int n, double epsilon = 1e-9) {
double x_prev = a > 1 ? a : 1.0; // Good initial guess
while (true) {
double x_next = ((n - 1) * x_prev + a / pow(x_prev, n - 1)) / n;
if (fabs(x_next - x_prev) < epsilon) {
break;
}
x_prev = x_next;
}
return x_prev;
}
vector<bool> primeNumbers(int N) {
vector<bool> isPrime(N + 1, 1);
isPrime[0] = isPrime[1] = 0;
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= N; j += i) {
isPrime[j] = 0;
}
}
}
return isPrime;
}
vector<int> fact, invFact;
void precompute(int N) {
fact.assign(N + 1, 1);
invFact.assign(N + 1, 1);
for (int i = 1; i <= N; i++) {
fact[i] = (fact[i - 1] * i) % MOD;
}
invFact[N] = binExpo(fact[N], MOD - 2);
for (int i = N - 1; i >= 0; i--) {
invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
}
}
// Compute nCr in O(1)
int precompute_nCr(int n, int r) {
if (r < 0 || r > n) {
return 0;
}
return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
}
int nCr(int n, int r) {
if (r < 0 || r > n) {
return 0;
}
if (r > n - r) {
r = n - r;
}
int numerator = 1;
for (int i = 0; i < r; i++) {
numerator = (numerator * (n - i)) % MOD;
}
int denominator = 1;
for (int i = 1; i <= r; i++) {
denominator = (denominator * i) % MOD;
}
return (numerator * binExpo(denominator, MOD - 2)) % MOD;
}
int longestCommonSubstring(string str1, string str2) {
int n = str1.size(), m = str2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
int mx_l = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
mx_l = max(mx_l, dp[i][j]);
}
}
}
return mx_l;
}
int rangeAND(int l, int r) {
if (l == r) {
return l;
}
unsigned int diff_bits = l ^ r;
unsigned int k = 64 - __builtin_clzll(diff_bits);
unsigned int mask = ~((1ULL << k) - 1);
return (l & mask);
}
int rangeOR(int l, int r) {
if (l == r) {
return l;
}
unsigned int diff_bits = l ^ r;
unsigned int k = 64 - __builtin_clzll(diff_bits);
unsigned int volatile_mask = (1ULL << k) - 1;
return (l | volatile_mask);
}
int computeXOR(int n) {
if (n % 4 == 0) {
return n;
}
if (n % 4 == 1) {
return 1;
}
if (n % 4 == 2) {
return n + 1;
}
return 0;
}
int max_xor(vector<int> v1) {
int mask = 0, ans = 0, n = v1.size();
for (int i = 32; i >= 0; i--) {
mask |= (1LL << i);
fast_set<int> s1;
for (int j = 0; j < n; j++) {
s1.insert((v1[j] & mask));
}
int candidate = ans | (1LL << i);
for (int prefix: s1) {
if (s1.find(prefix ^ candidate) != s1.end()) {
ans = candidate;
break;
}
}
}
return ans;
}
vector<int> xorAnalysis(const vector<int>& arr, int queryK = -1, int kth = -1) {
const int LOG = 60;
int basis[LOG] = {};
int sz = 0, total = 0;
auto insertVector = [&] (int x) {
total++;
for (int i = LOG - 1; i >= 0; i--) {
if (!(x >> i & 1)) {
continue;
}
if (!basis[i]) {
basis[i] = x;
sz++;
return;
}
x ^= basis[i];
}
};
for (auto x: arr) {
insertVector(x);
}
int maxXor = 0;
for (int i = LOG - 1; i >= 0; i--) {
maxXor = max(maxXor, maxXor ^ basis[i]);
}
int minXor = 0;
for (int i = 0; i < LOG; i++)
if (basis[i]) {
minXor = basis[i];
break;
}
auto canMake = [&] (int k) {
for (int i = LOG - 1; i >= 0; i--)
if (k >> i & 1) {
if (!basis[i])
return false;
k ^= basis[i];
}
return true;
};
bool possible = (queryK == -1 ? false : canMake(queryK));
int ways = 0;
if (queryK != -1 && possible) {
ways = 1LL << (total - sz);
}
int distinctCnt = 1LL << sz;
int kthXor = -1;
if (kth != -1 && kth < distinctCnt) {
vector<int> vals;
for (int i = 0; i < LOG; i++) {
if (basis[i]) {
vals.push_back(basis[i]);
}
}
for (int i = 0; i < vals.size(); i++) {
for (int j = 0; j < i; j++) {
if ((vals[i] ^ vals[j]) < vals[i]) {
vals[i] ^= vals[j];
}
}
}
sort(vals.begin(), vals.end());
int res = 0;
for (int i = 0; i < vals.size(); i++)
if (kth >> i & 1) {
res ^= vals[i];
}
kthXor = res;
}
return {
maxXor,
// [0] Max XOR
minXor,
// [1] Min non-zero XOR
possible,
// [2] Can make queryK? (1/0)
ways,
// [3] Number of subsets making queryK
distinctCnt,
// [4] Number of distinct XORs
kthXor // [5] k-th smallest XOR
};
}
int countSetBits(int n) {
int ans = 0;
for (int i = 0; (1LL << i) <= n; i++) {
int cycle = 1LL << (i + 1); // length of full cycle
int full_cycles = (n + 1) / cycle;
ans += full_cycles * (1LL << i); // contribution of complete cycles
int remainder = (n + 1) % cycle;
ans += max(0LL, remainder - (1LL << i)); // partial cycle contribution
}
return ans;
}
vector<int> positions_0_1(string str1) {
vector<int> pos_0;
vector<int> pos_1;
for (int i = str1.size() - 1; i >= 0; i--) {
if (str1[i] == '0') {
pos_0.push_back(i);
} else {
pos_1.push_back(i);
}
}
return (pos_1.size() <= pos_0.size() ? pos_1 : pos_0);
}
pair<int, pair<int, int>> subsequence_10_01_calculate(string str1) {
int sum1 = 0;
int lstIdx = str1.size() - 1;
vector<int> pos = positions_0_1(str1);
for (int i = 0; i < pos.size(); i++) {
sum1 += (lstIdx - pos[i] - i);
}
return {sum1, {pos.size(), str1[pos[0]] - '0'}};
}
pair<int, int> nos_01_10(string str1) {
pair<int, pair<int, int>> p1 = subsequence_10_01_calculate(str1);
if (p1.second.second) {
return {p1.first, ((str1.size() - p1.second.first) * p1.second.first) - p1.first};
}
return {((str1.size() - p1.second.first) * p1.second.first) - p1.first, p1.first};
}
int merge(vector<int>& arr, int st, int mid, int end) {
vector<int> temp;
int i = st, j = mid + 1;
int invCount = 0;
while (i <= mid && j <= end) {
if (arr[i] <= arr[j]) {
temp.push_back(arr[i]);
i++;
} else {
temp.push_back(arr[j]);
j++;
invCount += (mid - i + 1);
}
}
while (i <= mid) {
temp.push_back(arr[i++]);
}
while (j <= end) {
temp.push_back(arr[j++]);
}
for (int idx = 0; idx < temp.size(); idx++) {
arr[idx + st] = temp[idx];
}
return invCount;
}
int mergeSort(vector<int>& arr, int st, int end) {
if (st < end) {
int mid = st + (end - st) / 2;
int leftInvCount = mergeSort(arr, st, mid);
int rightInvCount = mergeSort(arr, mid + 1, end);
int invCount = merge(arr, st, mid, end);
return leftInvCount + rightInvCount + invCount;
}
return 0;
}
vector<int> factors(int n) {
vector<int> small, large;
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
small.push_back(i);
if (i != n / i) {
large.push_back(n / i);
}
}
}
reverse(large.begin(), large.end()); // Make the second half sorted
small.insert(small.end(), large.begin(), large.end()); // Combine both
return small;
}
// ---------------------------------------Prime Factors Start---------------------------------------
u64 mul(u64 a, u64 b, u64 mod) {
return (u128)a * b % mod;
}
u64 binpow(u64 a, u64 b, u64 mod) {
u64 res = 1;
while (b) {
if (b & 1)
res = mul(res, a, mod);
a = mul(a, a, mod);
b >>= 1;
}
return res;
}
bool is_prime(u64 n) {
if (n < 2)
return false;
for (u64 p: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
if (n % p == 0)
return n == p;
u64 d = n - 1, s = 0;
while ((d & 1) == 0)
d >>= 1, ++s;
u64 x = binpow(p, d, n);
if (x == 1 || x == n - 1)
continue;
bool ok = false;
for (u64 r = 1; r < s; ++r) {
x = mul(x, x, n);
if (x == n - 1) {
ok = true;
break;
}
}
if (!ok)
return false;
}
return true;
}
u64 pollard(u64 n) {
if (n % 2 == 0)
return 2;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
while (true) {
u64 c = rng() % (n - 1) + 1;
u64 x = rng() % (n - 1) + 1;
u64 y = x;
u64 d = 1;
while (d == 1) {
x = (mul(x, x, n) + c) % n;
y = (mul(y, y, n) + c) % n;
y = (mul(y, y, n) + c) % n;
d = gcd((u64)abs((int64_t)x - (int64_t)y), n);
}
if (d != n)
return d;
}
}
void factor(u64 n, vector<u64>& res) {
if (n == 1)
return;
if (dp_factors.count(n)) {
res.insert(res.end(), dp_factors[n].begin(), dp_factors[n].end());
return;
}
if (is_prime(n)) {
res.push_back(n);
dp_factors[n] = {n};
return;
}
u64 d = pollard(n);
vector<u64> res1, res2;
factor(d, res1);
factor(n / d, res2);
res.insert(res.end(), res1.begin(), res1.end());
res.insert(res.end(), res2.begin(), res2.end());
dp_factors[n] = res;
}
vector<int> prime_factors(u64 n) {
vector<u64> temp;
factor(n, temp);
sort(temp.begin(), temp.end()); // If you want to get the Factors in Sorted Manner
vector<int> result;
for (u64 x: temp)
result.push_back((int)x);
return result;
}
// ---------------------------------------Prime Factors End---------------------------------------
vector<u64> all_factors(u64 n) {
vector<u64> pf;
factor(n, pf); // uses your Pollard’s Rho + memo
sort(pf.begin(), pf.end());
// Count multiplicities
vector<pair<u64,int>> primes;
for (size_t i = 0; i < pf.size();) {
size_t j = i;
while (j < pf.size() && pf[j] == pf[i])
j++;
primes.emplace_back(pf[i], (int)(j - i));
i = j;
}
// Generate factors
vector<u64> factors = {1};
for (auto [p, cnt]: primes) {
size_t sz = factors.size();
u64 mul = 1;
for (int c = 1; c <= cnt; ++c) {
mul *= p;
for (size_t k = 0; k < sz; ++k)
factors.push_back(factors[k] * mul);
}
}
sort(factors.begin(), factors.end());
return factors;
}
multiset<int> m1;
int Find(int v, vector<int>& parent) {
if (v == parent[v]) {
return v;
}
return parent[v] = Find(parent[v], parent);
}
void Make(int v, vector<int>& size, vector<int>& parent) {
parent[v] = v;
size[v] = 1;
m1.insert(1);
}
void Union(int a, int b, vector<int>& size, vector<int>& parent) {
a = Find(a, parent);
b = Find(b, parent);
if (a != b) {
if (size[a] < size[b]) {
swap(a, b);
}
m1.erase(m1.find(size[a]));
m1.erase(m1.find(size[b]));
m1.insert(size[b] + size[a]);
parent[b] = a;
size[a] += size[b];
}
}
void dfs(int vertex, vector<int>& vis, vector<vector<int>>& g) {
// Take action on vertex after entering the vertex
vis[vertex] = true;
for (int child: g[vertex]) {
if (vis[child]) {
continue;
}
// Take action on child before entering the child node
dfs(child, vis, g);
// Take action on child after exiting the child node
}
// Take action on vertex before exiting the vertex
}
void bfs(int source, vector<bool>& vis, vector<int>& level, vector<vector<int>>& g) {
queue<int> q;
q.push(source);
vis[source] = true;
while (!q.empty()) {
int curr_v = q.front();
q.pop();
for (int child: g[curr_v]) {
if (!vis[child]) {
q.push(child);
vis[child] = true;
level[child] = level[curr_v] + 1;
}
}
}
}
bool detectCycleBFS(int source, vector<bool>& vis, vector<int>& level, vector<vector<int>>& g) {
queue<pair<int,int>> q; // {node, parent}
q.emplace(source, -1);
vis[source] = true;
while (!q.empty()) {
auto [curr_v, parent] = q.front();
q.pop();
for (int child: g[curr_v]) {
if (!vis[child]) {
q.emplace(child, curr_v);
vis[child] = true;
level[child] = level[curr_v] + 1;
} else if (child != parent) {
// ✅ Found a back edge → cycle exists
return true;
}
}
}
return false; // no cycle found in this BFS
}
void dijkstra(int source, int n, vector<int>& dist, vector<int>& parent, vector<vector<pair<int, int>>> g,
vector<int>& ways) {
int INF = 1e18;
dist.assign(n + 1, INF);
parent.assign(n + 1, 0);
dist[source] = 0;
ways[source] = 1;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.emplace(0, source);
while (!pq.empty()) {
int d = pq.top().first;
int v = pq.top().second;
pq.pop();
if (d > dist[v]) {
continue;
}
for (auto& edge: g[v]) {
int child_v = edge.first;
int wt = edge.second;
if (dist[v] + wt < dist[child_v]) {
dist[child_v] = dist[v] + wt;
parent[child_v] = v;
ways[child_v] = ways[v];
pq.emplace(dist[child_v], child_v);
} else if (dist[v] + wt == dist[child_v]) {
ways[child_v] = (ways[child_v] + ways[v]) % MOD;
}
}
}
}
int knapsack(vector<int>& v1, vector<int>& v2, int wt, int n, vector<vector<int>>& dp) {
if (wt == 0 || n == 0) {
return 0;
}
if (dp[n][wt] != -1) {
return dp[n][wt];
}
if (v1[n - 1] <= wt) {
return dp[n][wt] = max(v2[n - 1] + knapsack(v1, v2, wt - v1[n - 1], n - 1, dp),
knapsack(v1, v2, wt, n - 1, dp));
}
return dp[n][wt] = knapsack(v1, v2, wt, n - 1, dp);
}
bool ways(int idx, int n, int tar, int sum, vector<int>& v1, map<pair<int, int>, int>& mp1) {
if (idx > v1.size() - 1) {
return (sum == tar);
}
if (mp1.find({idx, sum}) != mp1.end()) {
return mp1[{idx, sum}];
}
return mp1[{idx, sum}] = (ways(idx + 1, n, tar, (sum + v1[idx]), v1, mp1) || ways(
idx + 1, n, tar, (sum ^ v1[idx]), v1, mp1));
}
bool isposs(vector<int>& v1, int mid) {
int min_n = v1.front();
for (int i = 1; i < v1.size(); i++) {
if (abs(v1[i] - v1[i - 1]) <= mid) {
min_n = min(min_n, v1[i]);
} else {
if (min_n > mid) {
return false;
}
min_n = v1[i];
}
}
if (min_n > mid) {
return false;
}
return true;
}
int recursive_BS(vector<int>& v1, int lo, int hi, int tar, int& ct1) {
ct1++;
if (lo > hi) {
return -1;
}
int mid = lo + ((hi - lo) >> 1);
if (v1[mid] == tar) {
return mid;
}
if (v1[mid] > tar) {
return recursive_BS(v1, lo, mid - 1, tar, ct1);
}
return recursive_BS(v1, mid + 1, hi, tar, ct1);
}
//Codeforces Blog - Link: https://codeforces.com/blog/entry/88760
#define all(x) (x).begin(), (x).end()
int Mod(int x) {
return (x %= MOD) < 0 ? x + MOD : x;
}
vector<int> Mul(const vector<int>& a, const vector<int>& b) {
const size_t n = a.size();
const size_t m = b.size();
vector<int> ret(n + m - 1, 0);
for (size_t i = 0; i < n; ++i) {
int ai = a[i] % MOD;
if (ai == 0)
continue;
for (size_t j = 0; j < m; ++j) {
ret[i + j] += (ai * (b[j] % MOD)) % MOD;
if (ret[i + j] >= MOD)
ret[i + j] -= MOD;
}
}
return ret;
}
vector<int> Div(const vector<int>& a, const vector<int>& b) {
vector<int> ret(all(a));
const size_t m = b.size();
// b is expected to be monic: highest coefficient = 1
for (int i = (int)ret.size() - 1; i >= (int)m - 1; --i) {
int coef = ret[(size_t)i] % MOD;
if (coef == 0)
continue;
// eliminate term of degree i using b
for (size_t j = 0; j + 1 < m; ++j) {
// skip highest term of b
size_t idx = (size_t)(i - (int)m + 1 + (int)j);
int val = ret[idx] - (coef * (b[j] % MOD)) % MOD;
if (val < 0)
val += MOD;
ret[idx] = val;
}
ret[(size_t)i] = 0; // eliminated
}
ret.resize(m - 1);
return ret;
}
/// A_{n} = \sum c_{i}A_{n-i} = \sum d_{i}A_{i}
// Example (0-indexed): nth Fibonacci => c = {1, 1}, a = {0, 1}; then F_n = kitamasa(c, a, n);
int kitamasa(const vector<int>& c, const vector<int>& a, int n) {
vector<int> d = {1}; // result
vector<int> xn = {0, 1}; // xn = x^1, x^2, x^4, ...
vector<int> f(c.size() + 1); // f(x) = x^K - \sum c_{i}x^{i}
f.back() = 1;
for (size_t i = 0; i < c.size(); i++) {
f[i] = Mod(-c[i]);
}
while (n) {
if (n & 1) {
d = Div(Mul(d, xn), f);
}
n >>= 1;
xn = Div(Mul(xn, xn), f);
}
int ret = 0;
for (size_t i = 0; i < a.size(); i++) {
ret = Mod(ret + a[i] * d[i]);
}
return ret;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin.exceptions(istream::failbit);
// #ifndef ONLINE_JUDGE
// freopen("F://My_Programs//GitHub_Repository//CPP//CodeChef//CodeChef//narrowing_down_input.txt", "r", stdin);
// freopen("F://My_Programs//GitHub_Repository//CPP//CodeChef//CodeChef//warm_up_output.txt", "w", stdout);
// #endif
vector<bool> v1 = primeNumbers(1e7);
int t;
cin >> t;
while (t--) {
int n, k, ct1 = 0, ct2 = 0, mul = 1;
cin >> n >> k;
if (k > ((n * (n - 1)) >> 1)) {
cout << -1 << endl;
continue;
}
bool flag = true;
for (int i = 2; i < 1e7; i++) {
if (((ct1 * (ct1 - 1)) >> 1) == k || (ct1 == n)) {
break;
}
if (v1[i]) {
if (((ct1 * (ct1 + 1)) >> 1) > k) {
flag = false;
break;
}
if (i != 2) {
if (mul > 500000000LL / i) {
flag = false;
break;
}
}
ct1++, ct2++;
cout << i << " ";
if (i != 2) {
mul *= i;
}
}
}
if (!flag && (ct2 + k - ((ct1 * (ct1 - 1)) >> 1) > n)) {
cout << -1 << endl;
continue;
}
if (!flag) {
for (int i = 0; i < k - ((ct1 * (ct1 - 1)) >> 1); i++) {
cout << mul << " ";
ct2++;
}
}
for (int i = 0; i < n - ct2; i++) {
cout << (mul << 1LL) << " ";
}
cout << endl;
}
return 0;
}