Joey is low on money. His friend Chandler wants to lend Joey some
money, but can’t give him directly, as Joey is too proud of himself to
accept it. So, in order to trick him, Chandler asks Joey to play a
game
In this game, Chandler gives Joey an array \(a_1, a_2, \dots, a_n\) (\(n \geq 2\)) of positive integers (\(a_i \ge 1\))
Joey can perform the following operation on the array any number of
times:
Take two indices \(i\) and \(j\)\((1 \le i
< j \le n)\)
Choose two integers \(x\) and \(y\) (\(x, y \ge
1\)) such that \(x \cdot y = a_i \cdot
a_j\)
Replace \(a_i\) by \(x\) and \(a_j\) by \(y\)
In the end, Joey will get the money equal to the sum
of elements of the final array
Find the maximum amount of money \(\mathrm{ans}\) Joey can get but
print\(2022 \cdot
\mathrm{ans}\). Why multiplied by \(2022\)? Because we are never gonna see it
again!
It is guaranteed that the product of all the elements of the array
\(a\) doesn’t exceed \(10^{12}\)
Input
Each test contains multiple test cases. The first line contains the
number of test cases \(t\) (\(1 \leq t \leq 4000\)). Description of the
test cases follows
The first line of each test case contains a single integer \(n\) (\(2 \leq n
\leq 50\)) — the length of the array \(a\)
The second line contains \(n\)
integers \(a_1, a_2, \dots, a_n\)
(\(1 \leq a_i \leq 10^6\)) — the array
itself
It’s guaranteed that the product of all \(a_i\) doesn’t exceed \(10^{12}\) (i. e. \(a_1 \cdot a_2 \cdot \ldots \cdot a_n \le
10^{12}\))
Output
For each test case, print the maximum money Joey can get
multiplied by\(2022\)
Example
input
1 2 3 4 5 6 7
3 3 2 3 2 2 1 3 3 1000000 1000000 1
output
1 2 3
28308 8088 2022000000004044
Note
In the first test case, Joey can do the following:
He chooses \(i = 1\) and \(j = 2\) (so he has \(a[i] \cdot a[j] = 6\)), chooses \(x = 6\) and \(y =
1\) and makes \(a[i] = 6\) and
\(a[j] = 1\).
Demodogs from the Upside-down have attacked Hawkins again. El wants
to reach Mike and also kill as many Demodogs in the way as possible
Hawkins can be represented as an \(n \times
n\) grid. The number of Demodogs in a cell at the \(i\)-th row and the \(j\)-th column is \(i \cdot j\). El is at position \((1, 1)\) of the grid, and she has to reach
\((n, n)\) where she can find Mike
The only directions she can move are the right (from \((i, j)\) to \((i,
j + 1)\)) and the down (from \((i,
j)\) to \((i + 1, j)\)). She
can’t go out of the grid, as there are doors to the Upside-down at the
boundaries
Calculate the maximum possible number of Demodogs \(\mathrm{ans}\) she can kill on the way,
considering that she kills all Demodogs in cells she visits (including
starting and finishing cells)
Print \(2022 \cdot \mathrm{ans}\)
modulo \(10^9 + 7\). Modulo \(10^9 + 7\) because the result can be too
large and multiplied by \(2022\)
because we are never gonna see it again!
(Note, you firstly multiply by \(2022\) and only after that
take the remainder.)
Input
Each test contains multiple test cases. The first line contains the
number of test cases \(t\) (\(1 \leq t \leq 10^4\)). Description of the
test cases follows
The first line of each test case contains one integer \(n\) (\(2 \leq n
\leq 10^9\)) — the size of the grid
Output
For each test case, print a single integer — the maximum number of
Demodogs that can be killed multiplied by \(2022\), modulo \(10^9 + 7\)
Example
input
1 2 3 4 5
4 2 3 50 1000000000
output
1 2 3 4
14154 44484 171010650 999589541
Note
In the first test case, for any path chosen by her the number of
Demodogs to be killed would be \(7\),
so the answer would be \(2022 \cdot 7 =
14154\)
You are given an integer array \(a_1, a_2,
\dots, a_n\) (\(1 \le a_i \le
n\))
Find the number of subarrays of \(a\) whose \(\operatorname{XOR}\) has an even number of
divisors. In other words, find all pairs of indices \((i, j)\) (\(i \le
j\)) such that \(a_i \oplus a_{i + 1}
\oplus \dots \oplus a_j\) has an even number of divisors
For example, numbers \(2\), \(3\), \(5\)
or \(6\) have an even number of
divisors, while \(1\) and \(4\) — odd. Consider that \(0\) has an odd number of divisors in this
task
Here \(\operatorname{XOR}\) (or
\(\oplus\)) denotes the bitwise
XOR operation
Print the number of subarrays but multiplied by 2022…
Okay, let’s stop. Just print the actual answer
Input
Each test contains multiple test cases. The first line contains the
number of test cases \(t\) (\(1 \leq t \leq 10^4\)). Description of the
test cases follows
The first line of each test case contains a single integer \(n\) (\(2 \leq n
\leq 2 \cdot 10^5\)) — the length of the array \(a\)
The second line contains \(n\)
integers \(a_1, a_2, \dots, a_n\)
(\(1 \leq a_i \leq n\))
It is guaranteed that the sum of \(n\) over all test cases does not exceed
\(2 \cdot 10^5\)
Output
For each test case, print the number of subarrays, whose \(\operatorname{XOR}\) has an even number of
divisors
Example
input
1 2 3 4 5 6 7 8 9
4 3 3 1 2 5 4 2 1 5 3 4 4 4 4 4 7 5 7 3 7 1 7 3
output
1 2 3 4
4 11 0 20
Note
In the first test case, there are \(4\) subarrays whose \(\operatorname{XOR}\) has an even number of
divisors: \([3]\), \([3,1]\), \([1,2]\), \([2]\)
In the second test case, there are \(11\) subarrays whose \(\operatorname{XOR}\) has an even number of
divisors: \([4,2]\), \([4,2,1]\), \([4,2,1,5]\), \([2]\), \([2,1]\), \([2,1,5]\), \([2,1,5,3]\), \([1,5,3]\), \([5]\), \([5,3]\), \([3]\)
In the third test case, there is no subarray whose \(\operatorname{XOR}\) has an even number of
divisors since \(\operatorname{XOR}\)
of any subarray is either \(4\) or
\(0\)
Game studio “DbZ Games” wants to introduce another map in their
popular game “Valiant”. This time, the map named “Panvel” will be based
on the city of Mumbai
Mumbai can be represented as \(n \times
m\) cellular grid. Each cell \((i,
j)\) (\(1 \le i \le n\); \(1 \le j \le m\)) of the grid is occupied by
a cuboid building of height \(a_{i,j}\)
This time, DbZ Games want to make a map that has perfect vertical
gameplay. That’s why they want to choose an \(l \times l\) square inside Mumbai, such
that each building inside the square has a height of at least \(l\)
Can you help DbZ Games find such a square of the maximum possible
size \(l\)?
Input
Each test contains multiple test cases. The first line contains the
number of test cases \(t\) (\(1 \leq t \leq 1000\)). Description of the
test cases follows
The first line of each test case contains two positive integers \(n\) and \(m\) (\(1 \le n
\le m\); \(1 \leq n \cdot m \leq
10^6\))
The \(i\)-th of next \(n\) lines contains \(m\) integers \(a_{i,1}, a_{i,2}, \dots, a_{i,m}\) (\(1 \leq a_{i,j} \leq 10^6\)) — heights of
buildings on the \(i\)-th row
It’s guaranteed that the sum of \(n \cdot
m\) over all test cases doesn’t exceed \(10^6\)
Output
For each test case, print the maximum side length \(l\) of the square DbZ Games can choose
In the first test case, we can choose the square of side \(l = 2\) (i. e. the whole grid) since the
heights of all buildings are greater than or equal to \(2\)
In the second test case, we can only choose the side as \(1\), so the answer is \(1\)
In the third test case, there are no squares of size \(2\) that have all buildings of height at
least \(2\), so the answer is \(1\)
public: RMQ_ST_2D() = delete; RMQ_ST_2D(query_func qfunc): qfunc(qfunc), f() {} template <typename init_func = std::function<data_t(size_t, size_t)>> voidinit(size_t n, size_t m, init_func ifunc) { constsize_t K = (size_t)std::log2(std::max(n, m)) + 1; f.resize(K); for (auto &i : f) { i.resize(n); for (auto &j : i) j.resize(m); } for (size_t i = 0; i < n; ++i) for (size_t j = 0; j < m; ++j) f[0][i][j] = ifunc(i, j); for (size_t k = 1, p = 1, q = 2; k < K; ++k, p = q, q *= 2) for (int i = 0; i + q - 1 < n; ++i) for (int j = 0; j + q - 1 < m; ++j) f[k][i][j] = qfunc(qfunc(f[k - 1][i][j], f[k - 1][i + p][j]), qfunc(f[k - 1][i][j + p], f[k - 1][i + p][j + p])); } data_tquery(size_t x, size_t y, size_t l)const{ size_t _ = (size_t)std::log2(l); returnqfunc(qfunc(f[_][x][y], f[_][x + l - (1 << _)][y]), qfunc(f[_][x][y + l - (1 << _)], f[_][x + l - (1 << _)][y + l - (1 << _)])); } }; autosolve([[maybe_unused]] int t_ = 0) -> void{ int n, m; cin >> n >> m; vvc<int> a(n, vc<int>(m)); for (auto &i : a) for (auto &j : i) cin >> j; RMQ_ST_2D<int> st([](int x, int y) { return min(x, y); }); st.init(n, m, [&](size_t x, size_t y) { return a[x][y]; }); auto check = [&](int g) { int mx = 0; for (int i = 0; i <= n - g; ++i) for (int j = 0; j <= m - g; ++j) mx = max(mx, st.query(i, j, g)); return mx >= g; }; int l = 1, r = min(n, m), ans = l; while (l <= r) { auto m = r - (r - l) / 2; if (check(m)) l = (ans = m) + 1; else r = m - 1; } cout << ans << '\n'; } intmain(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int i_ = 0; int t_ = 0; std::cin >> t_; for (i_ = 0; i_ < t_; ++i_) solve(i_); return0; }
E - Graph Cost
You are given an initially empty undirected graph with \(n\) nodes, numbered from \(1\) to \(n\) (i. e. \(n\) nodes and \(0\) edges). You want to add \(m\) edges to the graph, so the graph won’t
contain any self-loop or multiple edges
If an edge connecting two nodes \(u\) and \(v\) is added, its weight must be equal to
the greatest common divisor of \(u\)
and \(v\), i. e. \(\gcd(u, v)\)
In order to add edges to the graph, you can repeat the following
process any number of times (possibly zero):
choose an integer \(k \ge 1\);
add exactly \(k\) edges to the
graph, each having a weight equal to \(k +
1\). Adding these \(k\) edges
costs \(k + 1\) in total
Note that you can’t create self-loops or multiple edges. Also, if you
can’t add \(k\) edges of weight \(k + 1\), you can’t choose such \(k\)
For example, if you can add \(5\)
more edges to the graph of weight \(6\), you may add them, and it will cost
\(6\) for the whole pack of \(5\) edges. But if you can only add \(4\) edges of weight \(6\) to the graph, you can’t perform this
operation for \(k = 5\)
Given two integers \(n\) and \(m\), find the minimum total cost to form a
graph of \(n\) vertices and exactly
\(m\) edges using the operation above.
If such a graph can’t be constructed, output \(-1\)
Note that the final graph may consist of several connected
components
Input
Each test contains multiple test cases. The first line contains the
number of test cases \(t\) (\(1 \leq t \leq 10^4\)). Description of the
test cases follows
The first line of each test case contains two integers \(n\) and \(m\) (\(2 \leq n
\leq 10^6\); \(1 \leq m \leq
\frac{n(n-1)}{2}\))
It is guaranteed that the sum of \(n\) over all test cases does not exceed
\(10^6\)
Output
For each test case, print the minimum cost to build the graph, or
\(-1\) if you can’t build such a
graph
Example
input
1 2 3 4 5
4 4 1 6 10 9 4 10 11
output
1 2 3 4
2 -1 7 21
Note
In the first test case, we can add an edge between the vertices \(2\) and \(4\) with \(\gcd =
2\). This is the only possible way to add \(1\) edge that will cost \(2\)
In the second test case, there is no way to add \(10\) edges, so the answer is \(-1\)
In the third test case, we can add the following edges:
\(k = 1\): edge of weight \(2\) between vertices \(2\) and \(4\) (\(\gcd(2, 4)
= 2\)). Cost: \(2\);
\(k = 1\): edge of weight \(2\) between vertices \(4\) and \(6\) (\(\gcd(4, 6)
= 2\)). Cost: \(2\);
Suppose you have an integer array \(a_1,
a_2, \dots, a_n\)
Let \(\operatorname{lsl}(i)\) be the
number of indices \(j\) (\(1 \le j < i\)) such that \(a_j < a_i\)
Analogically, let \(\operatorname{grr}(i)\) be the number of
indices \(j\) (\(i < j \le n\)) such that \(a_j > a_i\)
Let’s name position \(i\) good in
the array \(a\) if \(\operatorname{lsl}(i) <
\operatorname{grr}(i)\)
Finally, let’s define a function \(f\) on array \(a\)\(f(a)\) as the sum of all
\(a_i\) such that \(i\) is good in \(a\)
Given two integers \(n\) and \(k\), find the sum of \(f(a)\) over all arrays \(a\) of size \(n\) such that \(1
\leq a_i \leq k\) for all \(1 \leq i
\leq n\) modulo \(998\,244\,353\)
Input
The first and only line contains two integers \(n\) and \(k\) (\(1 \leq n
\leq 50\); \(2 \leq k <
998\,244\,353\))
Output
Output a single integer — the sum of \(f\) over all arrays \(a\) of size \(n\) modulo \(998\,244\,353\)
Joey is low on money. His friend Chandler wants to lend Joey some
money, but can’t give him directly, as Joey is too proud of himself to
accept it. So, in order to trick him, Chandler asks Joey to play a
game
In this game, Chandler gives Joey an array \(a_1, a_2, \dots, a_n\) (\(n \geq 2\)) of positive integers (\(a_i \ge 1\))
Joey can perform the following operation on the array any number of
times:
Take two indices \(i\) and \(j\)\((1 \le i
< j \le n)\)
Choose two integers \(x\) and \(y\) (\(x, y \ge
1\)) such that \(x \cdot y = a_i \cdot
a_j\)
Replace \(a_i\) by \(x\) and \(a_j\) by \(y\)
In the end, Joey will get the money equal to the sum
of elements of the final array
Find the maximum amount of money \(\mathrm{ans}\) Joey can get but
print\(2022 \cdot
\mathrm{ans}\). Why multiplied by \(2022\)? Because we are never gonna see it
again!
It is guaranteed that the product of all the elements of the array
\(a\) doesn’t exceed \(10^{12}\)
Input
Each test contains multiple test cases. The first line contains the
number of test cases \(t\) (\(1 \leq t \leq 4000\)). Description of the
test cases follows
The first line of each test case contains a single integer \(n\) (\(2 \leq n
\leq 50\)) — the length of the array \(a\)
The second line contains \(n\)
integers \(a_1, a_2, \dots, a_n\)
(\(1 \leq a_i \leq 10^6\)) — the array
itself
It’s guaranteed that the product of all \(a_i\) doesn’t exceed \(10^{12}\) (i. e. \(a_1 \cdot a_2 \cdot \ldots \cdot a_n \le
10^{12}\))
Output
For each test case, print the maximum money Joey can get
multiplied by\(2022\)
Example
input
1 2 3 4 5 6 7
3 3 2 3 2 2 1 3 3 1000000 1000000 1
output
1 2 3
28308 8088 2022000000004044
Note
In the first test case, Joey can do the following:
He chooses \(i = 1\) and \(j = 2\) (so he has \(a[i] \cdot a[j] = 6\)), chooses \(x = 6\) and \(y =
1\) and makes \(a[i] = 6\) and
\(a[j] = 1\).
Demodogs from the Upside-down have attacked Hawkins again. El wants
to reach Mike and also kill as many Demodogs in the way as possible
Hawkins can be represented as an \(n \times
n\) grid. The number of Demodogs in a cell at the \(i\)-th row and the \(j\)-th column is \(i \cdot j\). El is at position \((1, 1)\) of the grid, and she has to reach
\((n, n)\) where she can find Mike
The only directions she can move are the right (from \((i, j)\) to \((i,
j + 1)\)) and the down (from \((i,
j)\) to \((i + 1, j)\)). She
can’t go out of the grid, as there are doors to the Upside-down at the
boundaries
Calculate the maximum possible number of Demodogs \(\mathrm{ans}\) she can kill on the way,
considering that she kills all Demodogs in cells she visits (including
starting and finishing cells)
Print \(2022 \cdot \mathrm{ans}\)
modulo \(10^9 + 7\). Modulo \(10^9 + 7\) because the result can be too
large and multiplied by \(2022\)
because we are never gonna see it again!
(Note, you firstly multiply by \(2022\) and only after that
take the remainder.)
Input
Each test contains multiple test cases. The first line contains the
number of test cases \(t\) (\(1 \leq t \leq 10^4\)). Description of the
test cases follows
The first line of each test case contains one integer \(n\) (\(2 \leq n
\leq 10^9\)) — the size of the grid
Output
For each test case, print a single integer — the maximum number of
Demodogs that can be killed multiplied by \(2022\), modulo \(10^9 + 7\)
Example
input
1 2 3 4 5
4 2 3 50 1000000000
output
1 2 3 4
14154 44484 171010650 999589541
Note
In the first test case, for any path chosen by her the number of
Demodogs to be killed would be \(7\),
so the answer would be \(2022 \cdot 7 =
14154\)
You are given an integer array \(a_1, a_2,
\dots, a_n\) (\(1 \le a_i \le
n\))
Find the number of subarrays of \(a\) whose \(\operatorname{XOR}\) has an even number of
divisors. In other words, find all pairs of indices \((i, j)\) (\(i \le
j\)) such that \(a_i \oplus a_{i + 1}
\oplus \dots \oplus a_j\) has an even number of divisors
For example, numbers \(2\), \(3\), \(5\)
or \(6\) have an even number of
divisors, while \(1\) and \(4\) — odd. Consider that \(0\) has an odd number of divisors in this
task
Here \(\operatorname{XOR}\) (or
\(\oplus\)) denotes the bitwise
XOR operation
Print the number of subarrays but multiplied by 2022…
Okay, let’s stop. Just print the actual answer
Input
Each test contains multiple test cases. The first line contains the
number of test cases \(t\) (\(1 \leq t \leq 10^4\)). Description of the
test cases follows
The first line of each test case contains a single integer \(n\) (\(2 \leq n
\leq 2 \cdot 10^5\)) — the length of the array \(a\)
The second line contains \(n\)
integers \(a_1, a_2, \dots, a_n\)
(\(1 \leq a_i \leq n\))
It is guaranteed that the sum of \(n\) over all test cases does not exceed
\(2 \cdot 10^5\)
Output
For each test case, print the number of subarrays, whose \(\operatorname{XOR}\) has an even number of
divisors
Example
input
1 2 3 4 5 6 7 8 9
4 3 3 1 2 5 4 2 1 5 3 4 4 4 4 4 7 5 7 3 7 1 7 3
output
1 2 3 4
4 11 0 20
Note
In the first test case, there are \(4\) subarrays whose \(\operatorname{XOR}\) has an even number of
divisors: \([3]\), \([3,1]\), \([1,2]\), \([2]\)
In the second test case, there are \(11\) subarrays whose \(\operatorname{XOR}\) has an even number of
divisors: \([4,2]\), \([4,2,1]\), \([4,2,1,5]\), \([2]\), \([2,1]\), \([2,1,5]\), \([2,1,5,3]\), \([1,5,3]\), \([5]\), \([5,3]\), \([3]\)
In the third test case, there is no subarray whose \(\operatorname{XOR}\) has an even number of
divisors since \(\operatorname{XOR}\)
of any subarray is either \(4\) or
\(0\)
Game studio “DbZ Games” wants to introduce another map in their
popular game “Valiant”. This time, the map named “Panvel” will be based
on the city of Mumbai
Mumbai can be represented as \(n \times
m\) cellular grid. Each cell \((i,
j)\) (\(1 \le i \le n\); \(1 \le j \le m\)) of the grid is occupied by
a cuboid building of height \(a_{i,j}\)
This time, DbZ Games want to make a map that has perfect vertical
gameplay. That’s why they want to choose an \(l \times l\) square inside Mumbai, such
that each building inside the square has a height of at least \(l\)
Can you help DbZ Games find such a square of the maximum possible
size \(l\)?
Input
Each test contains multiple test cases. The first line contains the
number of test cases \(t\) (\(1 \leq t \leq 1000\)). Description of the
test cases follows
The first line of each test case contains two positive integers \(n\) and \(m\) (\(1 \le n
\le m\); \(1 \leq n \cdot m \leq
10^6\))
The \(i\)-th of next \(n\) lines contains \(m\) integers \(a_{i,1}, a_{i,2}, \dots, a_{i,m}\) (\(1 \leq a_{i,j} \leq 10^6\)) — heights of
buildings on the \(i\)-th row
It’s guaranteed that the sum of \(n \cdot
m\) over all test cases doesn’t exceed \(10^6\)
Output
For each test case, print the maximum side length \(l\) of the square DbZ Games can choose
In the first test case, we can choose the square of side \(l = 2\) (i. e. the whole grid) since the
heights of all buildings are greater than or equal to \(2\)
In the second test case, we can only choose the side as \(1\), so the answer is \(1\)
In the third test case, there are no squares of size \(2\) that have all buildings of height at
least \(2\), so the answer is \(1\)
public: RMQ_ST_2D() = delete; RMQ_ST_2D(query_func qfunc): qfunc(qfunc), f() {} template <typename init_func = std::function<data_t(size_t, size_t)>> voidinit(size_t n, size_t m, init_func ifunc) { constsize_t K = (size_t)std::log2(std::max(n, m)) + 1; f.resize(K); for (auto &i : f) { i.resize(n); for (auto &j : i) j.resize(m); } for (size_t i = 0; i < n; ++i) for (size_t j = 0; j < m; ++j) f[0][i][j] = ifunc(i, j); for (size_t k = 1, p = 1, q = 2; k < K; ++k, p = q, q *= 2) for (int i = 0; i + q - 1 < n; ++i) for (int j = 0; j + q - 1 < m; ++j) f[k][i][j] = qfunc(qfunc(f[k - 1][i][j], f[k - 1][i + p][j]), qfunc(f[k - 1][i][j + p], f[k - 1][i + p][j + p])); } data_tquery(size_t x, size_t y, size_t l)const{ size_t _ = (size_t)std::log2(l); returnqfunc(qfunc(f[_][x][y], f[_][x + l - (1 << _)][y]), qfunc(f[_][x][y + l - (1 << _)], f[_][x + l - (1 << _)][y + l - (1 << _)])); } }; autosolve([[maybe_unused]] int t_ = 0) -> void{ int n, m; cin >> n >> m; vvc<int> a(n, vc<int>(m)); for (auto &i : a) for (auto &j : i) cin >> j; RMQ_ST_2D<int> st([](int x, int y) { return min(x, y); }); st.init(n, m, [&](size_t x, size_t y) { return a[x][y]; }); auto check = [&](int g) { int mx = 0; for (int i = 0; i <= n - g; ++i) for (int j = 0; j <= m - g; ++j) mx = max(mx, st.query(i, j, g)); return mx >= g; }; int l = 1, r = min(n, m), ans = l; while (l <= r) { auto m = r - (r - l) / 2; if (check(m)) l = (ans = m) + 1; else r = m - 1; } cout << ans << '\n'; } intmain(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int i_ = 0; int t_ = 0; std::cin >> t_; for (i_ = 0; i_ < t_; ++i_) solve(i_); return0; }
E - Graph Cost
You are given an initially empty undirected graph with \(n\) nodes, numbered from \(1\) to \(n\) (i. e. \(n\) nodes and \(0\) edges). You want to add \(m\) edges to the graph, so the graph won’t
contain any self-loop or multiple edges
If an edge connecting two nodes \(u\) and \(v\) is added, its weight must be equal to
the greatest common divisor of \(u\)
and \(v\), i. e. \(\gcd(u, v)\)
In order to add edges to the graph, you can repeat the following
process any number of times (possibly zero):
choose an integer \(k \ge 1\);
add exactly \(k\) edges to the
graph, each having a weight equal to \(k +
1\). Adding these \(k\) edges
costs \(k + 1\) in total
Note that you can’t create self-loops or multiple edges. Also, if you
can’t add \(k\) edges of weight \(k + 1\), you can’t choose such \(k\)
For example, if you can add \(5\)
more edges to the graph of weight \(6\), you may add them, and it will cost
\(6\) for the whole pack of \(5\) edges. But if you can only add \(4\) edges of weight \(6\) to the graph, you can’t perform this
operation for \(k = 5\)
Given two integers \(n\) and \(m\), find the minimum total cost to form a
graph of \(n\) vertices and exactly
\(m\) edges using the operation above.
If such a graph can’t be constructed, output \(-1\)
Note that the final graph may consist of several connected
components
Input
Each test contains multiple test cases. The first line contains the
number of test cases \(t\) (\(1 \leq t \leq 10^4\)). Description of the
test cases follows
The first line of each test case contains two integers \(n\) and \(m\) (\(2 \leq n
\leq 10^6\); \(1 \leq m \leq
\frac{n(n-1)}{2}\))
It is guaranteed that the sum of \(n\) over all test cases does not exceed
\(10^6\)
Output
For each test case, print the minimum cost to build the graph, or
\(-1\) if you can’t build such a
graph
Example
input
1 2 3 4 5
4 4 1 6 10 9 4 10 11
output
1 2 3 4
2 -1 7 21
Note
In the first test case, we can add an edge between the vertices \(2\) and \(4\) with \(\gcd =
2\). This is the only possible way to add \(1\) edge that will cost \(2\)
In the second test case, there is no way to add \(10\) edges, so the answer is \(-1\)
In the third test case, we can add the following edges:
\(k = 1\): edge of weight \(2\) between vertices \(2\) and \(4\) (\(\gcd(2, 4)
= 2\)). Cost: \(2\);
\(k = 1\): edge of weight \(2\) between vertices \(4\) and \(6\) (\(\gcd(4, 6)
= 2\)). Cost: \(2\);
Suppose you have an integer array \(a_1,
a_2, \dots, a_n\)
Let \(\operatorname{lsl}(i)\) be the
number of indices \(j\) (\(1 \le j < i\)) such that \(a_j < a_i\)
Analogically, let \(\operatorname{grr}(i)\) be the number of
indices \(j\) (\(i < j \le n\)) such that \(a_j > a_i\)
Let’s name position \(i\) good in
the array \(a\) if \(\operatorname{lsl}(i) <
\operatorname{grr}(i)\)
Finally, let’s define a function \(f\) on array \(a\)\(f(a)\) as the sum of all
\(a_i\) such that \(i\) is good in \(a\)
Given two integers \(n\) and \(k\), find the sum of \(f(a)\) over all arrays \(a\) of size \(n\) such that \(1
\leq a_i \leq k\) for all \(1 \leq i
\leq n\) modulo \(998\,244\,353\)
Input
The first and only line contains two integers \(n\) and \(k\) (\(1 \leq n
\leq 50\); \(2 \leq k <
998\,244\,353\))
Output
Output a single integer — the sum of \(f\) over all arrays \(a\) of size \(n\) modulo \(998\,244\,353\)