We are given an array $$$a$$$ and need to find the maximum length subsequence $$$b$$$ such that for every adjacent pair:

This means that every pair of consecutive elements in the subsequence must share at least one common set bit.

Key Observation

Two elements can be adjacent in the subsequence if and only if their bitwise AND is non-zero, i.e., they share at least one common bit.

Instead of working with values directly, we can think in terms of bits (from $$$0$$$ to $$$32$$$).

Approach

Define a DP array:

We process the array from left to right.

For each element $$$a_i$$$:

1. Find all bits that are set in $$$a_i$$$
2. Compute:

If no such bit exists (i.e., all corresponding $$$dp[b] = 0$$$), then $$$best = 1$$$.
3. For every bit $$$b$$$ set in $$$a_i$$$, update:

Special Case

If $$$a_i = 0$$$, it has no set bits and cannot be adjacent to any element. It can only form a subsequence of length $$$1$$$.

Answer

The final answer is:

Time complexity: $$$O(N \log (\max A))$$$

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds; 
template<typename T> inline void input(T& x) {cin >> x;}
template<typename T, typename... S> inline void input(T& x, S&... args) {cin >> x; input(args ...);}
template<typename T> inline void print(T x) {cout << x << '\n';}
template<typename T, typename... S> inline void print(T x, S... args) {cout << x << ' '; print(args ...);}
#define debug(...) cout << #__VA_ARGS__ << ": "; print(__VA_ARGS__);
#define rep(i, a, b) for (auto i = (a); i < (b); i++)
#define arrput(l) for (auto &i : l) {cin >> i;}
#define arrprint(l) for (auto i : l) {cout << i << ' ';} cout << '\n'
#define setup() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define int long long
#define endl '\n'
#define all(x) x.begin(), x.end()
#define sz(x) ((int) (x.size()))
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 
typedef vector<int> vi; typedef pair<int, int> pii;
const int MOD = (int) 1e9 + 7; //998244353;

int32_t main() {
	setup(); int tc; input(tc); while (tc--) {
		int n;
		input(n);

		vi a(n);
		arrput(a);

		vi dp(n + 1, 0), x(32, 0);
		rep(i, 0, n) {
			dp[i + 1] = 1;
			rep(j, 0, 32) {
				if (a[i] >> j & 1) {
					dp[i + 1] = max(dp[i + 1], dp[x[j]] + 1);
					x[j] = i + 1;
				}
			}
		}
		print(*max_element(all(dp)));
	}
}

The first observation is that we must choose $$$A_j \le A_i$$$, otherwise there aren't enough bowls to place the cooked noodles in. Given $$$A_j \le A_i$$$, we wish to find the number of arrangements of empty and full bowls that can be formed. This is given by $$$\binom{A_i}{A_j}$$$.

It can be seen that if $$$\binom{A_i}{A_j}$$$ is odd, then Siddhant wins the game and in all other cases Pramit wins the game. To find the number of pairs $$$(i, j)$$$, $$$i \ne j$$$ s.t. $$$\binom{A_i}{A_j}$$$ is odd, we can use Lucas's Theorem. It tells us that $$$\binom{A_i}{A_j}$$$ is odd iff $$$A_j$$$ is a submask of $$$A_i$$$, i.e.,

where & represents the bitwise AND operator.

We now need to compute

This can be efficiently computed using sum of subsets DP. First create an array $$$F$$$ of length $$$2^k$$$, where $$$k$$$ is the smallest integer s.t. $$$2^k \ge N$$$ and $$$F_x$$$ is the frequency of $$$x$$$ in $$$A$$$. Then we shall compute another array $$$G$$$ using sum of subsets defined as the following.

The final answer is given by

Time complexity: $$$O(N \log N)$$$

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds; 
template<typename T> inline void input(T& x) {cin >> x;}
template<typename T, typename... S> inline void input(T& x, S&... args) {cin >> x; input(args ...);}
template<typename T> inline void print(T x) {cout << x << '\n';}
template<typename T, typename... S> inline void print(T x, S... args) {cout << x << ' '; print(args ...);}
#define debug(...) cout << #__VA_ARGS__ << ": "; print(__VA_ARGS__);
#define rep(i, a, b) for (auto i = (a); i < (b); i++)
#define arrput(l) for (auto &i : l) {cin >> i;}
#define arrprint(l) for (auto i : l) {cout << i << ' ';} cout << '\n'
#define setup() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define int long long
#define endl '\n'
#define all(x) x.begin(), x.end()
#define sz(x) ((int) (x.size()))
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 
typedef vector<int> vi; typedef pair<int, int> pii;
const int MOD = (int) 1e9 + 7; //998244353;

int32_t main() {
	setup(); int tc; input(tc); while (tc--) {
		int n;
		input(n);

		vi a(n);
		arrput(a);

		int x = 1, k = 0;
		while (x <= n) {
			x *= 2;
			k++;
		}

		vi f(x);
		for (int i : a) {
			f[i]++;
		}

		vi g = f;
		rep(b, 0, k) {
			rep(i, 0, x) {
				if (i & (1 << b)) {
					g[i] += g[i ^ (1 << b)];
				}
			}
		}

		int res = 0;
		rep(i, 0, x) {
			res += f[i] * (g[i] - f[i]);
			res += f[i] * (f[i] - 1);
		}
		print(res);
	}
}

We construct a matrix $$$B$$$ of size $$$N \times K$$$ where $$$B_{i, j}$$$ is $$$1$$$ iff vertex $$$i$$$ is good with respect to tree $$$j$$$. This matrix can be precomputed simply doing a DFS starting from vertex $$$a_j$$$ in each tree and setting all values of $$$B_{i, j}$$$ to $$$1$$$ for each $$$i$$$ in the subtree of $$$a_j$$$.

Having computed this matrix, it is easy to see that queries reduce to checking whether the rows $$$B_u$$$ and $$$B_v$$$ are equal. Naive equality-checking for these vectors can be done to answer the queries in $$$O(K)$$$, however this is too slow for our problem. We can speed this up to $$$O(K/64)$$$ per query by using bitsets, but this is also too slow. To resolve queries in $$$O(1)$$$, we use hashing.

Instead of comparing $$$B_u$$$ and $$$B_v$$$, we compare $$$H(B_u)$$$ and $$$H(B_v)$$$, where $$$H(V)$$$ is some function that hashes a bit vector $$$V$$$. Hashes can be precomputed and then used to solve queries in $$$O(1)$$$.

There are multiple methods of hashing that could be used to solve the problem. Most participants who solved the problem in contest used either polynomial-hashing or XOR-hashing.

Time complexity: $$$O(NK + Q)$$$

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds; 
template<typename T> inline void input(T& x) {cin >> x;}
template<typename T, typename... S> inline void input(T& x, S&... args) {cin >> x; input(args ...);}
template<typename T> inline void print(T x) {cout << x << '\n';}
template<typename T, typename... S> inline void print(T x, S... args) {cout << x << ' '; print(args ...);}
#define debug(...) cout << #__VA_ARGS__ << ": "; print(__VA_ARGS__);
#define rep(i, a, b) for (auto i = (a); i < (b); i++)
#define arrput(l) for (auto &i : l) {cin >> i;}
#define arrprint(l) for (auto i : l) {cout << i << ' ';} cout << '\n'
#define setup() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define int long long
#define endl '\n'
#define all(x) x.begin(), x.end()
#define sz(x) ((int) (x.size()))
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 
typedef vector<int> vi; typedef pair<int, int> pii;
const int MOD = (int) 1e9 + 7; //998244353;

void dfs(int u, int w, int p, vector<vi> &graph, vi &a) {
	a[u] = a[u] or (u == w);
	for (int v : graph[u]) {
		if (v != p) {
			a[v] = a[u];
			dfs(v, w, u, graph, a);
		}
	}
}

int32_t main() {
	setup();

	int n, k, q;
	input(n, k, q);

	vector<vi> a(k, vi(n, false));
	rep(i, 0, k) {
		int w;
		input(w);
		w--;

		vector<vi> graph(n);
		rep(j, 0, n - 1) {
			int u, v;
			input(u, v);
			graph[u - 1].push_back(v - 1);
			graph[v - 1].push_back(u - 1);
		}

		dfs(0, w, -1, graph, a[i]);
	}

	vi b(n);
	rep(i, 0, k) {
		rep(j, 0, n) {
			b[j] = (2 * b[j] + a[i][j]) % MOD;
		}
	}

	while (q--) {
		int u, v;
		input(u, v);

		u--;
		v--;

		if (b[u] == b[v]) {
			print("YES");
		}
		else {
			print("NO");
		}
	}
}

Refer to solution $$$2$$$ of the lite version.

The interference condition gives the same 2-SAT clauses as the easy version. For the range exclusivity condition, each query $$$(u, L, R)$$$ requires $$$C_u \ne C_v$$$ for all $$$v \in [L, R]$$$. How many clauses does this naively generate?

Each query naively generates $$$O(N)$$$ clauses, giving $$$O(NQ)$$$ total, but this is too slow. Can you add implications to a range of nodes in $$$O(\log N)$$$ using a segment tree built on the implication graph?

Define boolean variable $$$C_i$$$ where $$$C_i = \texttt{true}$$$ means channel $$$A$$$ and $$$C_i = \texttt{false}$$$ means channel $$$B$$$. Each variable $$$C_i$$$ is represented by node $$$2i$$$ and its negation $$$\neg C_i$$$ by node $$$2i+1$$$.

$$$\textbf{Interference Condition:}$$$

For each $$$i$$$ from $$$0$$$ to $$$N-2$$$, compute the validity of all four source combinations:

Each invalid combination is forbidden via an implication. Recall that the clause $$$(x \lor y)$$$ is equivalent to $$$(\neg x \Rightarrow y)$$$ and $$$(\neg y \Rightarrow x)$$$:

where $$$\text{add_implication}(u, v)$$$ adds both $$$u \Rightarrow v$$$ and $$$\neg v \Rightarrow \neg u$$$.

$$$\textbf{Range Exclusivity Condition:}$$$

For each query $$$(u, L, R)$$$, we need $$$C_u \ne C_v$$$ for all $$$v \in [L, R],\ v \ne u$$$, meaning exactly one of $$$u, v$$$ is picked from channel $$$A$$$. This gives:

$$$\textbf{Segment Tree on Implication Graph:}$$$

Build four segment trees over indices $$$0 \ldots N-1$$$ directly as nodes in the implication graph:

$$$\texttt{IN_POS}$$$: top-down tree over $$$C_i$$$ (a single edge into a node propagates to all $$$C_v$$$ in a range), $$$\texttt{IN_NEG}$$$: top-down tree over $$$\neg C_i$$$ (same, for $$$\neg C_v$$$), $$$\texttt{OUT_POS}$$$: bottom-up tree over $$$C_i$$$ (all $$$C_v$$$ in a range imply a single target), $$$\texttt{OUT_NEG}$$$: bottom-up tree over $$$\neg C_i$$$ (same, for $$$\neg C_v$$$).

Leaf nodes of all four trees are connected directly to the corresponding $$$C_i$$$ or $$$\neg C_i$$$ variable nodes, so implications propagate correctly to actual variables.

For each query $$$(u, L, R)$$$ (with $$$u$$$ excluded), four sets of implications are added in $$$O(\log N)$$$ each:

When $$$u \in [L, R]$$$, the query is split into $$$[L, u-1]$$$ and $$$[u+1, R]$$$ to exclude $$$u$$$.

Run 2-SAT on the implication graph, and check for satisfiability. $$$O(N)$$$ nodes and edges for the four segment trees, $$$O(Q \log N)$$$ edges for range queries, $$$O(N + Q \log N)$$$ for Kosaraju's SCC , overall $$$\mathcal{O}(N + Q \log N)$$$.

1. Cost for a Single String (1-Indexed)

A palindrome possesses perfect reflectional symmetry across its center. To make an arbitrary string $$$T$$$ of length $$$m$$$ a palindrome, the characters in its first half must perfectly match their corresponding characters in the second half. Using 1-based indexing, we check characters from index 1 up to the midpoint $$$\lfloor \frac{m}{2} \rfloor$$$. The minimum number of replacement operations required is:

2. Triple Summation for All Substrings

A substring is defined as any contiguous sequence of characters within the main string $$$S$$$, denoted by a starting index $$$l$$$ and an ending index $$$r$$$, subject to the bounds $$$1 \le l \le r \le n$$$. To compute the total replacement cost across all possible substrings of a string $$$S$$$ of length $$$n$$$, we embed the single-string cost formula into a double summation over all valid boundaries $$$l$$$ and $$$r$$$:

3. Contribution to the Sum (Change of Variables)

To evaluate this summation we try to change indices. We can iterate over every character pair $$$(i, j)$$$, where $$$1\le i \lt j \lt n$$$. To do this $$$i$$$ must equal $$$l+k-1$$$ and $$$j$$$ must equal $$$r-k+1$$$. Written in terms of $$$k$$$, $$$k = i -l +1$$$ and $$$k=r-j+1$$$.

To achieve this, the limits must also change. $$$l$$$ and $$$r$$$ offer natural mappings to $$$i$$$ and $$$j$$$, given that $$$l \le i$$$ and $$$j \le r$$$. To deal with $$$k$$$ we consider that for every $$$k$$$, it can be expressed in terms of the other variable as: $$$k=i -l +1=r-j+1$$$.

$$$\implies i-l= r-j = d$$$,

where $$$d$$$ is a non negative number. We encapsulate this degree of freedom by defining bounds on $$$d$$$.

1. $$$l=i-d$$$
2. $$$r = j+d$$$

Because $$$1 \le l$$$ and $$$r \le n$$$,

1. $$$1 \le i -d \implies d \le i-1$$$
2. $$$j + d \le n \implies d \le n-j$$$

Since both the bounds have to satisfy, $$$d_{max} = min(i-1, n-j)$$$

The summation then transforms to

Since, the summation term doesnt depend on d, this further reduces to

Speedups

Naively computing this is $$$O(n^2)$$$. But notice that for a fixed $$$j$$$, the $$$min$$$ formula only changes behaviour once, when $$$i \gt n-j+1$$$. But $$$i$$$ also has to be less than $$$j$$$, so the point where it flips is $$$L = min(j-1,n-j+1)$$$

This splits our inner loop into two clean parts:

1. For $$$i \in [1, L]$$$, the minimum is always $$$i$$$.
2. For $$$i \in [L + 1, j - 1]$$$, the minimum is always $$$n - j + 1$$$.

We can calculate the summation of the inner loop in $$$O(1)$$$ by assuming that all of the $$$s[i]$$$ are mismatches with $$$s[j]$$$ and then subtracting the contribution of characters that match with $$$s[j]$$$. In that case, the first term can be computed with a prefix array that stores the sum of $$$i$$$ over all ranges. The second term is just $$$(n- j + 1)* (j-L-1 - x)$$$, where $$$x$$$ denotes the matches with $$$s[j]$$$ in $$$[L + 1, j - 1]$$$.

Time complexity: $$$O(n * |\alpha|)$$$, where $$$|\alpha|$$$ is the length of the alphabet.

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds; 
template<typename T> inline void input(T& x) {cin >> x;}
template<typename T, typename... S> inline void input(T& x, S&... args) {cin >> x; input(args ...);}
template<typename T> inline void print(T x) {cout << x << '\n';}
template<typename T, typename... S> inline void print(T x, S... args) {cout << x << ' '; print(args ...);}
#define debug(...) cout << #__VA_ARGS__ << ": "; print(__VA_ARGS__);
#define rep(i, a, b) for (auto i = (a); i < (b); i++)
#define arrput(l) for (auto &i : l) {cin >> i;}
#define arrprint(l) for (auto i : l) {cout << i << ' ';} cout << '\n'
#define setup() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define int long long
#define endl '\n'
#define all(x) x.begin(), x.end()
#define sz(x) ((int) (x.size()))
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 
typedef vector<int> vi; typedef pair<int, int> pii;
const int MOD = (int) 1e9 + 7; //998244353;

int32_t main() {
	setup(); int tc; input(tc); while (tc--) {
		int n;
		input(n);

		string s;
		input(s);

		vector<vi> p(n + 1, vi(26, 0)), q(n + 1, vi(26, 0));
		rep(i, 0, n) {
			p[i + 1] = p[i];
			p[i + 1][s[i] - 'a'] += i + 1;

			q[i + 1] = q[i];
			q[i + 1][s[i] - 'a']++;
		}

		int res = 0;
		rep(i, 0, n) {
			int l = min((int) i, n - i - 1);
			res += (l + 1) * (l + 2) / 2 - p[l + 1][s[i] - 'a'];
			res += (n - i) * ((i - l) - (q[i + 1][s[i] - 'a'] - q[l + 1][s[i] - 'a']));
		}
		print(res);
	}
}

Can you solve this problem in $$$O(N)$$$?

Since we are allowed $$$n \cdot m$$$ attempts to catch the kangaroo, it sufficies to try every combination of $$$(a, b)$$$, such that $$$0 \le a \lt n, 0 \le b \lt m$$$. At time $$$t$$$ ($$$1 \le t \le n \cdot m$$$), we test for $$$a_t = \lfloor \frac {t-1}{m} \rfloor$$$ and $$$b_t = (t - 1) \% m$$$. where $$$x \% y$$$ denotes the modulo operator (remainder when dividing $$$x$$$ by $$$y$$$).

We can construct a sequence $$$v_t$$$ of length $$$n \cdot m$$$ to test for each $$$(a_t, b_t)$$$. That is,

for $$$1 \le t \le n \cdot m$$$.

Time complexity: $$$O(n \cdot m)$$$

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds; 
template<typename T> inline void input(T& x) {cin >> x;}
template<typename T, typename... S> inline void input(T& x, S&... args) {cin >> x; input(args ...);}
template<typename T> inline void print(T x) {cout << x << '\n';}
template<typename T, typename... S> inline void print(T x, S... args) {cout << x << ' '; print(args ...);}
#define debug(...) cout << #__VA_ARGS__ << ": "; print(__VA_ARGS__);
#define rep(i, a, b) for (auto i = (a); i < (b); i++)
#define arrput(l) for (auto &i : l) {cin >> i;}
#define arrprint(l) for (auto i : l) {cout << i << ' ';} cout << '\n'
#define setup() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define int long long
#define endl '\n'
#define all(x) x.begin(), x.end()
#define sz(x) ((int) (x.size()))
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 
typedef vector<int> vi; typedef pair<int, int> pii;
const int MOD = (int) 1e9 + 7; //998244353;

int32_t main() {
	setup();

	int n, m;
	input(n, m);

	vi res;
	int t = 1;
	rep(a, 0, n) {
		rep(b, 0, m) {
			res.push_back(a + t * b);
			t++;
		}
	}
	arrprint(res);
}

We shall first attempt to solve the decision version of this problem. That is, by doing some (possibly zero) operations with a total cost $$$\le X$$$, we want to find if it is possible to make the median of the array $$$\le Z$$$ for some integer $$$Z$$$. Once we have solved this problem, we can simply use binary search to find the smallest value of $$$Z$$$ for which there exists a solution.

To make the median of $$$A$$$ less than or equal to $$$Z$$$, we must ensure that there are at least $$$\lceil \frac{N}{2} \rceil$$$ elements in the final array that are $$$\le Z$$$. To do this, we calculate $$$cost_i$$$, the minimum cost of making $$$A_i \le Z$$$.

If for some $$$1 \le x \lt y \le M$$$, we have $$$C_x \gt C_y$$$, it is never optimal to choose $$$k=x$$$ over $$$k=y$$$. Thus, we can calculate $$$C'_k = \displaystyle \min_{x \ge k} {(C_x)}$$$, the "real" cost of operation $$$k$$$. Now we have $$$C'_1 \le C'_2 \le \dots C'_M$$$.

The next observation is that we never perform an operation with $$$k \gt 30$$$. This is because for any $$$A_i \le 10^9$$$, $$$\lfloor A_i^{1/30} \rfloor$$$ is equal to $$$1$$$. From now, we shall only consider the $$$29$$$ operations corresponding to $$$k \in [2, 30]$$$. We also notice that for any $$$k \ge 2$$$, the value of $$$A_i$$$ after the operation is atmost $$$\sqrt {10^9} \le 4 \cdot 10^4$$$.

For all $$$1 \le x \le 4 \cdot 10^4$$$, we calculate $$$dp_x$$$, the minimum cost of making $$$x \le Z$$$. For all $$$x \le Z$$$, $$$dp_x$$$ is set to $$$0$$$ and for all $$$x \gt Z$$$, we calculate $$$dp_x$$$ as

Using $$$dp$$$, we can calculate $$$cost_i$$$ for each $$$1 \le i \le N$$$. If $$$A_i \le Z$$$, $$$cost_i = 0$$$. Otherwise if $$$A_i \le 4 \cdot 10^4$$$, we simply have $$$cost_i = dp_{A_i}$$$. Finally if $$$A_i \gt Z$$$ and $$$A_i \gt 4 \cdot 10^4$$$ we have

After calculating all $$$cost_i$$$, we can simply sort the array and take the sum of the smallest $$$\lceil \frac{N}{2} \rceil$$$ values from this array. This is minimum cost of making the median $$$\le Z$$$. By comparing this value with $$$X$$$, we can solve the decision version of the problem and by extension the original problem as well.

Time complexity: $$$O((N + \sqrt {\max A})\log^2(\max A))$$$

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds; 
template<typename T> inline void input(T& x) {cin >> x;}
template<typename T, typename... S> inline void input(T& x, S&... args) {cin >> x; input(args ...);}
template<typename T> inline void print(T x) {cout << x << '\n';}
template<typename T, typename... S> inline void print(T x, S... args) {cout << x << ' '; print(args ...);}
#define debug(...) cout << #__VA_ARGS__ << ": "; print(__VA_ARGS__);
#define rep(i, a, b) for (auto i = (a); i < (b); i++)
#define arrput(l) for (auto &i : l) {cin >> i;}
#define arrprint(l) for (auto i : l) {cout << i << ' ';} cout << '\n'
#define setup() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define int long long
#define endl '\n'
#define all(x) x.begin(), x.end()
#define sz(x) ((int) (x.size()))
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 
typedef vector<int> vi; typedef pair<int, int> pii;
const int MOD = (int) 1e9 + 7; //998244353;

const int N = 4e4;
vector<vi>p(N + 1);

int invpow(int x, int k) {
	int l = 2, r = x, res = 1;
	while (l <= r) {
		int m = (l + r) / 2;
		int y = 1;
		rep(j, 0, k) {
			y *= m;
			if (y > x) {
				break;
			}
		}
		if (y <= x) {
			res = m;
			l = m + 1;
		}
		else {
			r = m - 1;
		}
	}
	return res;
}

int get(vi &a, vi &c, int u, vector<vi> &q) {
	vi dp(N + 1, 2e18);
	rep(x, 0, N + 1) {
		if (x <= u) {
			dp[x] = 0;
			continue;
		}

		dp[x] = 2e18;
		rep(i, 2, sz(c)) {
			int z = i < sz(p[x]) ? p[x][i] : 1;
			dp[x] = min(dp[x], dp[z] + c[i]);
			if (z == 1) {
				break;
			}
		}
	}

	vi v;
	rep(j, 0, sz(a)) {
		int x = a[j];
		if (x <= u) {
			v.push_back(0);
			continue;
		}

		int t = 2e18;
		rep(i, 2, sz(c)) {
			int z = i < sz(q[j]) ? q[j][i] : 1;
			t = min(t, dp[z] + c[i]);
			if (z == 1) {
				break;
			}
		}
		v.push_back(t);
	}

	sort(all(v));
	int res = 0;
	rep(i, 0, (sz(a) + 1) / 2) {
		res += v[i];
		if (res > (int) 2e18) {
			return res;
		}
	}
	return res;
}

int32_t main() {
	setup();

	int n, m, x;
	input(n, m, x);

	vi a(n), c(m);
	arrput(a);
	arrput(c);

	c.insert(c.begin(), 0);
	for (int i = m - 1; i >= 0; i--) {
		c[i] = min(c[i], c[i + 1]);
	}
	m = min(m, 30ll);
	c.resize(m + 1);

	rep(i, 1, N + 1) {
		p[i].resize(m + 1);
		rep(j, 2, m + 1) {
			p[i][j] = invpow(i, j);
			if (p[i][j] == 1) {
				break;
			}
		}
	}

	vector<vi> q(n);
	rep(i, 0, n) {
		q[i].resize(m + 1);
		rep(j, 2, m + 1) {
			q[i][j] = invpow(a[i], j);
			if (q[i][j] == 1) {
				break;
			}
		}
	}

	int l = 1, r = 1e9, res = 1e9;
	while (l <= r) {
		int u = (l + r) / 2;
		if (get(a, c, u, q) <= x) {
			res = u;
			r = u - 1;
		}
		else {
			l = u + 1;
		}
	}
	print(res);
}

The problem asks us to find a hidden integer $$$X$$$ (where $$$0 \le X \lt 10^{16}$$$) using at most 67 queries of the form $$$\gcd(X + M, N)$$$.

Core Observation

We can determine the binary representation of $$$X$$$ bit by bit, from the least significant bit to the most significant bit. We do this by choosing $$$N$$$ to be consecutive powers of $$$2$$$.

Suppose we have built an offset $$$M$$$ such that $$$X + M$$$ is a multiple of $$$2^{i-1}$$$. Mathematically, this means:

We want to determine if $$$X + M$$$ is also a multiple of $$$2^i$$$. We can find out by querying with $$$N = 2^i$$$.

• Case 1: If $$$\gcd(X+M, 2^i) = 2^i$$$, then $$$X + M \equiv 0 \pmod{2^i}$$$. The $$$i$$$-th bit of $$$X + M$$$ is 0. We do not need to change $$$M$$$.
• Case 2: If $$$\gcd(X+M, 2^i) = 2^{i-1}$$$, then $$$X + M \not\equiv 0 \pmod{2^i}$$$. The $$$i$$$-th bit of $$$X + M$$$ is 1. To carry this bit over and make $$$X + M$$$ a multiple of $$$2^i$$$, we must add $$$2^{i-1}$$$ to $$$M$$$.

Step-by-Step Construction

1. Initialization: To ensure $$$M$$$ and $$$N$$$ remain valid positive integers ($$$ \lt 10^{18}$$$) and to avoid negative number edge cases during intermediate steps, we initialize $$$M$$$ with a large power of 2 strictly greater than the maximum possible value of $$$X$$$. Since $$$X \lt 10^{16} \lt 2^{54}$$$, we start with an offset $$$M = 2^{54}$$$. We set $$$N = 1$$$ to track our current power of 2.
2. Iterating Over the Bits: Since the maximum value is strictly less than $$$2^{54}$$$, we need to resolve exactly 54 bits. We can imagine a loop running 54 times (from bit $$$i = 1$$$ to 54). In each iteration: — We multiply $$$N$$$ by 2 (so $$$N$$$ becomes $$$2^i$$$). — We query $$$\gcd(M, N)$$$. — If the returned value is not $$$N$$$, it means the current bit is 1. We correct our offset by updating $$$M = M + N/2$$$.
3. Extracting $$$X$$$: After checking all 54 bits, we have successfully forced $$$X + M$$$ to be a multiple of $$$2^{54}$$$. Because we initially added a baseline of $$$2^{54}$$$ to $$$M$$$, we first subtract $$$2^{54}$$$ from our accumulated $$$M$$$. Since $$$X$$$ is strictly less than $$$2^{54}$$$, the hidden value $$$X$$$ is simply the difference required to reach the next multiple of $$$2^{54}$$$ from $$$M$$$. If $$$M = 0$$$, then $$$X = 0$$$; otherwise, $$$X = N - M$$$.

Complexity

• Query Complexity: Since $$$10^{16} \lt 2^{54}$$$, we only need to test 54 bits. The loop runs exactly 54 times per testcase, requiring 54 queries. This comfortably satisfies the 67 query limit.
• Time Complexity: $$$O(\log X)$$$ per testcase, as we perform constant-time operations for each bit.
• Space Complexity: $$$O(1)$$$ auxiliary space.

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds; 
template<typename T> inline void input(T& x) {cin >> x;}
template<typename T, typename... S> inline void input(T& x, S&... args) {cin >> x; input(args ...);}
template<typename T> inline void print(T x) {cout << x << '\n';}
template<typename T, typename... S> inline void print(T x, S... args) {cout << x << ' '; print(args ...);}
#define debug(...) cout << #__VA_ARGS__ << ": "; print(__VA_ARGS__);
#define rep(i, a, b) for (auto i = (a); i < (b); i++)
#define arrput(l) for (auto &i : l) {cin >> i;}
#define arrprint(l) for (auto i : l) {cout << i << ' ';} cout << '\n'
#define setup() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define int long long
#define endl '\n'
#define all(x) x.begin(), x.end()
#define sz(x) ((int) (x.size()))
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 
typedef vector<int> vi; typedef pair<int, int> pii;
const int MOD = (int) 1e9 + 7; //998244353;

bool debug = false;
int X = -1, K = 67;

int query(int m, int n) {
	// assert(K--);
	if (debug) {
		return gcd(m + X, n);
	}
	print('?', m, n);
	cout.flush();
	int g;
	input(g);
	assert(g != -1);
	return g;
}

int32_t main() {
	int tc; input(tc); while (tc--) {
		K = 67;
		if (debug) {
			input(X);
		}

		int m = 1ll << 54, n = 1;
		while (n <= (int) 1e16) {
			n *= 2;
			if (query(m, n) != n) {
				m += n / 2;
			}
		}
		m -= 1ll << 54;

		int res = m == 0 ? 0 : n - m;
		// int res = n - m;
		print('!', res);
		cout.flush();

		if (debug) {
			assert(res == X);
		}
		else {
			input(res);
			assert(res != -1);
		}
	}
}