Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Use Bézout first: has an integer solution exactly when . Here and . The all-zero case is not valid because .
Set and . For fixed positive , choosing uniquely determines and , so you only need to count valid values.
Let be the number of triples with positive where and . Then , where counts exact . Recover by descending inclusion-exclusion over multiples.
For a fixed value , the valid middle values are . Compare with bit by bit; breaks into only binary-trie subtrees.
For each , insert the trie subtrees for every positive multiple of , then query the same sets again. Two trie subtrees intersect only when one is an ancestor of the other, so subtree sums plus ancestor counts give fast. Then add the separate cases where exactly one XOR is .
Research basis: the official Codeforces editorial for 2205G and a Luogu writeup both point to the same core route: Bézout, Möbius/inclusion-exclusion over the gcd, and a binary-trie way to count intersections of XOR-threshold sets. The explanation below is original and uses a descending exact-gcd sieve instead of writing the Möbius formula directly.
Let
By Bézout's theorem, the equation
has an integer solution iff
The only annoying corner is : then the left side is always , but , so it is invalid. Do not sweep this under the rug; it is exactly the kind of tiny zero case that makes 3000-rated problems laugh at you.
Since , every XOR value is at most . Indeed, if , then both numbers use fewer than bits, so their XOR is .
First count only the case and .
For fixed positive , once is chosen, the values
are forced. So the number of triples for this pair is
where
Now define
This counts all positive-XOR triples where both XOR values are divisible by . If is the number of positive-XOR triples with exact , then
So after computing every for , recover exact gcd counts by descending over multiples:
Then the positive-XOR contribution is
So the real problem is computing every quickly.
For a fixed value , we need the set
with the extra restriction . Use a binary trie over all -bit numbers, since .
Let . While comparing with from high bit to low bit:
Thus every decomposes into trie subtrees. Since the full trie also contains values above , each subtree is counted with size clipped to .
For one fixed , enumerate all positive multiples . Insert the subtree decomposition of each into a trie-node multiset. For each selected trie node , store:
When querying another selected node , its intersection with an inserted selected node is nonzero only in two cases:
So if is the number of inserted selected nodes on the ancestor chain of , the query contribution is
Summing this over all selected nodes of all multiples gives exactly
The implementation uses a heap-indexed complete binary trie. During insertion, the selected side subtrees are updated directly, and only the single tight path is recomputed upward. That keeps each inserted at , not .
Finally handle zero-XOR cases:
So add
Complexity per test case, with and :
Memory is . Since the sum of all is at most , this fits comfortably in the intended limits.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int B = 20;
const int U = 1 << B;
const int NODE_COUNT = 1 << (B + 1);
int m_cur, x_lim, lim_cur;
int cnt_node[NODE_COUNT], seen[NODE_COUNT];
ll sum_node[NODE_COUNT];
vector<int> touched;
int stamp_id = 1;
inline int clippedSize(int l, int r) {
if (l > m_cur) return 0;
r = min(r, m_cur);
return r - l + 1;
}
inline void touch(int u) {
if (seen[u] != stamp_id) {
seen[u] = stamp_id;
touched.push_back(u);
}
}
void addSet(int v) {
int node = 1, l = 0, r = U - 1;
int path_node[B], path_size[B], depth = 0;
for (int bit = B - 1; bit >= 0; --bit) {
path_node[depth] = node;
path_size[depth] = clippedSize(l, r);
++depth;
int mid = (l + r) >> 1;
int vb = (v >> bit) & 1;
if ((x_lim >> bit) & 1) {
int side_bit = vb;
int side = (node << 1) | side_bit;
int sl = side_bit ? mid + 1 : l;
int sr = side_bit ? r : mid;
int sz = clippedSize(sl, sr);
if (sz) {
touch(side);
++cnt_node[side];
sum_node[side] += sz;
}
int next_bit = vb ^ 1;
node = (node << 1) | next_bit;
if (next_bit) l = mid + 1;
else r = mid;
} else {
int next_bit = vb;
node = (node << 1) | next_bit;
if (next_bit) l = mid + 1;
else r = mid;
}
}
for (int i = depth - 1; i >= 0; --i) {
int u = path_node[i];
ll nxt = 1LL * cnt_node[u] * path_size[i]
+ sum_node[u << 1]
+ sum_node[(u << 1) | 1];
if (sum_node[u] != nxt) {
touch(u);
sum_node[u] = nxt;
}
}
}
ll querySet(int v) {
ll res = 0;
int ancestors = 0;
int node = 1, l = 0, r = U - 1;
for (int bit = B - 1; bit >= 0; --bit) {
ancestors += cnt_node[node];
int mid = (l + r) >> 1;
int vb = (v >> bit) & 1;
if ((x_lim >> bit) & 1) {
int side_bit = vb;
int side = (node << 1) | side_bit;
int sl = side_bit ? mid + 1 : l;
int sr = side_bit ? r : mid;
int sz = clippedSize(sl, sr);
if (sz) res += sum_node[side] + 1LL * ancestors * sz;
int next_bit = vb ^ 1;
node = (node << 1) | next_bit;
if (next_bit) l = mid + 1;
else r = mid;
} else {
int next_bit = vb;
node = (node << 1) | next_bit;
if (next_bit) l = mid + 1;
else r = mid;
}
}
return res;
}
void clearTrie() {
for (int u : touched) {
cnt_node[u] = 0;
sum_node[u] = 0;
}
touched.clear();
++stamp_id;
}
ll calcDivisible(int step) {
for (int v = step; v <= lim_cur; v += step) addSet(v);
ll res = 0;
for (int v = step; v <= lim_cur; v += step) res += querySet(v);
clearTrie();
return res;
}
int countSetSize(int v) {
int res = 0;
int node = 1, l = 0, r = U - 1;
for (int bit = B - 1; bit >= 0; --bit) {
int mid = (l + r) >> 1;
int vb = (v >> bit) & 1;
if ((x_lim >> bit) & 1) {
int side_bit = vb;
int sl = side_bit ? mid + 1 : l;
int sr = side_bit ? r : mid;
res += clippedSize(sl, sr);
int next_bit = vb ^ 1;
node = (node << 1) | next_bit;
if (next_bit) l = mid + 1;
else r = mid;
} else {
int next_bit = vb;
node = (node << 1) | next_bit;
if (next_bit) l = mid + 1;
else r = mid;
}
}
return res;
}
void solveCase() {
int n;
cin >> n >> m_cur;
x_lim = m_cur + 1;
lim_cur = 2 * m_cur;
vector<ll> exact(lim_cur + 1);
for (int d = 1; d <= lim_cur; ++d) exact[d] = calcDivisible(d);
for (int d = lim_cur; d >= 1; --d) {
for (int multiple = d + d; multiple <= lim_cur; multiple += d) {
exact[d] -= exact[multiple];
}
}
ll ans = 0;
for (int g = 1; g <= lim_cur; ++g) {
if (n % g == 0) {
ans += exact[g];
ans += 2LL * countSetSize(g);
}
}
cout << ans << '\n';
}
int main() {
setIO();
touched.reserve(NODE_COUNT);
int tc;
cin >> tc;
while (tc--) solveCase();
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int B = 20;
const int U = 1 << B;
const int NODE_COUNT = 1 << (B + 1);
int m_cur, x_lim, lim_cur;
int cnt_node[NODE_COUNT], seen[NODE_COUNT];
ll sum_node[NODE_COUNT];
vector<int> touched;
int stamp_id = 1;
inline int clippedSize(int l, int r) {
if (l > m_cur) return 0;
r = min(r, m_cur);
return r - l + 1;
}
inline void touch(int u) {
if (seen[u] != stamp_id) {
seen[u] = stamp_id;
touched.push_back(u);
}
}
void addSet(int v) {
int node = 1, l = 0, r = U - 1;
int path_node[B], path_size[B], depth = 0;
for (int bit = B - 1; bit >= 0; --bit) {
path_node[depth] = node;
path_size[depth] = clippedSize(l, r);
++depth;
int mid = (l + r) >> 1;
int vb = (v >> bit) & 1;
if ((x_lim >> bit) & 1) {
int side_bit = vb;
int side = (node << 1) | side_bit;
int sl = side_bit ? mid + 1 : l;
int sr = side_bit ? r : mid;
int sz = clippedSize(sl, sr);
if (sz) {
touch(side);
++cnt_node[side];
sum_node[side] += sz;
}
int next_bit = vb ^ 1;
node = (node << 1) | next_bit;
if (next_bit) l = mid + 1;
else r = mid;
} else {
int next_bit = vb;
node = (node << 1) | next_bit;
if (next_bit) l = mid + 1;
else r = mid;
}
}
for (int i = depth - 1; i >= 0; --i) {
int u = path_node[i];
ll nxt = 1LL * cnt_node[u] * path_size[i]
+ sum_node[u << 1]
+ sum_node[(u << 1) | 1];
if (sum_node[u] != nxt) {
touch(u);
sum_node[u] = nxt;
}
}
}
ll querySet(int v) {
ll res = 0;
int ancestors = 0;
int node = 1, l = 0, r = U - 1;
for (int bit = B - 1; bit >= 0; --bit) {
ancestors += cnt_node[node];
int mid = (l + r) >> 1;
int vb = (v >> bit) & 1;
if ((x_lim >> bit) & 1) {
int side_bit = vb;
int side = (node << 1) | side_bit;
int sl = side_bit ? mid + 1 : l;
int sr = side_bit ? r : mid;
int sz = clippedSize(sl, sr);
if (sz) res += sum_node[side] + 1LL * ancestors * sz;
int next_bit = vb ^ 1;
node = (node << 1) | next_bit;
if (next_bit) l = mid + 1;
else r = mid;
} else {
int next_bit = vb;
node = (node << 1) | next_bit;
if (next_bit) l = mid + 1;
else r = mid;
}
}
return res;
}
void clearTrie() {
for (int u : touched) {
cnt_node[u] = 0;
sum_node[u] = 0;
}
touched.clear();
++stamp_id;
}
ll calcDivisible(int step) {
for (int v = step; v <= lim_cur; v += step) addSet(v);
ll res = 0;
for (int v = step; v <= lim_cur; v += step) res += querySet(v);
clearTrie();
return res;
}
int countSetSize(int v) {
int res = 0;
int node = 1, l = 0, r = U - 1;
for (int bit = B - 1; bit >= 0; --bit) {
int mid = (l + r) >> 1;
int vb = (v >> bit) & 1;
if ((x_lim >> bit) & 1) {
int side_bit = vb;
int sl = side_bit ? mid + 1 : l;
int sr = side_bit ? r : mid;
res += clippedSize(sl, sr);
int next_bit = vb ^ 1;
node = (node << 1) | next_bit;
if (next_bit) l = mid + 1;
else r = mid;
} else {
int next_bit = vb;
node = (node << 1) | next_bit;
if (next_bit) l = mid + 1;
else r = mid;
}
}
return res;
}
void solveCase() {
int n;
cin >> n >> m_cur;
x_lim = m_cur + 1;
lim_cur = 2 * m_cur;
vector<ll> exact(lim_cur + 1);
for (int d = 1; d <= lim_cur; ++d) exact[d] = calcDivisible(d);
for (int d = lim_cur; d >= 1; --d) {
for (int multiple = d + d; multiple <= lim_cur; multiple += d) {
exact[d] -= exact[multiple];
}
}
ll ans = 0;
for (int g = 1; g <= lim_cur; ++g) {
if (n % g == 0) {
ans += exact[g];
ans += 2LL * countSetSize(g);
}
}
cout << ans << '\n';
}
int main() {
setIO();
touched.reserve(NODE_COUNT);
int tc;
cin >> tc;
while (tc--) solveCase();
}